ARC150F Solution
irris
·
·
题解
900 AC，写篇题解。
首先，存在一个子结构，那就是「所有和为 m 的子序列」必然蕴含了「所有和 \leq m-1 的子序列」。基于此，可以得到一个 O(s^2\log n) 的做法：
- 设 f_i = j 表示最小的 j 满足 a_1, \ldots, a_j 包含所有和为 i 的子序列。
- 枚举子序列的最后一个元素的值，有转移
f_i = \max_{k=1}^i \operatorname{nxt}(f_{i-k}, k),
其中 \operatorname{nxt}(i, j) 表示 a_i 后第一个 = j 的下标，容易做到 O(n) 预处理单次 O(\log n) 查询。
- 由于 $\operatorname{nxt}(i, j) > i$，若 $\operatorname{nxt}(f_{i-k}, k) \leq f_m$，则显然不如 $f_m$ 的转移；
- 否则，此时必然有 $\operatorname{nxt}(f_{i-k}, k) = \operatorname{nxt}(f_m, k)$。
因此，此时每种 $k$ 的可能转移到的位置 **构成一个区间且值相等**，可以通过求 $\operatorname{nxt}$ 的逆运算，排序双指针后确定它们，随后将 $f$ 放在线段树上维护即可。
时间复杂度 $O(s\log s\log ns)$。