题解：AT_arc150_f [ARC150F] Constant Sum Subsequence

· · 题解

[ARC150F] Constant Sum Subsequence

神奇分治题。

设 f_i 表示任意总和为 i 的序列都被表达出来的所需要的最短前缀是多少，设 nxt_{i,j} 表示第 i 个位置后面第一个为 j 在那个位置，有转移：

f_i=\max_{j}\ nxt_{f_j,i-j}

这个转移看上去就很鬼畜，不太好优化，考虑分治。

对于一个区间 [l,r]，我们考虑 [l,mid] 中的数对 [mid+1,r] 中的数的贡献，但受限于这个需要记录两个东西的 nxt，我们还是不好做。

注意到分治过程中区间长度的总和是 \operatorname{O}(n\log n) 的，而转移中 nxt 的第二维在分治过程中每一次只有区间长度种，所以可以考虑枚举第二维。

接下来考虑找一些性质。

结论 1： 对于所有的 x,y,k 满足 x<y，如果 nxt_{x,k}\neq nxt_{y,k}，那么一定有 nxt_{x,k}\le y。

证明：

首先 nxt_{x,k} 一定是小于 nxt_{y,k} 的，而如果存在 y< nxt_{x,k}\le nxt_{y,k}，就代表第 nxt_{x,k} 个位置的值是 k，那么 nxt_{y,k} 就会是 nxt_{x,k}，违背了最初的条件。

结论 2：如果 l\le x\le mid,\ nxt_{f_x,k}\neq nxt_{f_{mid},k}，那么我们不需要考虑 f_x 对 mid+1\sim r 中的 f 值的影响。

证明：

首先 f 是有单调性的，所以 f_x\le f_{mid}。

根据结论 1 我们可以得到 nxt_{f_x,k}\le f_{mid}，而根据定义对于任意的 k， nxt_{f_{mid},k}>f_{mid}，所以说 f_x 在这种情况下一定不如 f_{mid}。

考虑对于一个 k 有哪些 x 是必要的。由于 nxt_{x,k}\le nxt_{x+1,k}，所以实际上是有一段区间会对后面进行转移。我们可以找到 f_{mid} 前面的第一个 k 在哪里，设为 p，那么对于 f_x>p 的 x 都是有意义的。

于是我们要做的事情就变成了每次对一个区间取 \max，用线段树维护即可，时间复杂度 \operatorname{O}(n\log n+s\log^2 s)。

code