ARC150F 题解

EuphoricStar · 2022-12-14 18:43:55 · 题解

定义 \mathrm{nxt}(i,x) 为最小的 j 满足 a_j = x 且 j > i，\mathrm{pre}(i,x) 为最大的 j 满足 a_j = x 且 j < i。

有了上面的定义后，考虑 dp。设 f_s 表示最小的 i，满足所有和为 s 的正整数序列都是 a_1,a_2,...,a_i 的子序列。则答案为 f_S（此处的 S 为原题面中的 S），初值 f_0 = 0。

考虑如何转移。枚举一个数 x，那么所有和为 s-x 的序列都可以在末尾接上一个 x 得到，所以 f_s \ge \mathrm{nxt}(f_{s-x},x)。可得 f_s = \max\limits_{x=1}^s \mathrm{nxt}(f_{s-x},x)。如果使用刷表法，则 f_s 已知，f_{s+x} \gets \max(f_{s+x},\mathrm{nxt}(f_s,x))。这样朴素转移是 O(S^2 \log n + n) 的。

考虑分治优化。设当前区间为 [l,r]，令 mid = \left\lfloor\frac{l+r}{2}\right\rfloor。先计算 [l,mid]，再考虑 [l,mid] 对 [mid+1,r] 的贡献。还是先枚举一个 x，由 f 的转移式可得 f 有单调性，则 \forall i \in [mid+1,r],f_i > f_{mid}。则我们只需要考虑可能对右区间有贡献的 s，即 s 满足 \mathrm{nxt}(f_s,x) = \mathrm{nxt}(f_{mid},x)。这些 s 形成了一段区间，而这个区间的左端点就是最小的 i 满足 f_i \ge \mathrm{pre}(f_{mid},x)。于是对这段区间内的 s，令 f_{s+x} \gets \max(f_{s+x},\mathrm{nxt}(f_{mid},x))。则我们需要一个区间取 \max，单点查询的数据结构。可以用标记永久化的线段树实现。

总时间复杂度 O(n + S \log S(\log S + \log n))。

code