题解：AT_arc150_f [ARC150F] Constant Sum Subsequence

神奇分治题。

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

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

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

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

接下来考虑找一些性质。

证明：

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

证明：

首先 $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)$。