CF2092F Andryusha and CCB 题解

可能唯一难度是位置的题目。调和级数板题放 D 题一万个人能过。

设字符串为 $z_1z_2\cdots z_n$，记 $s_i=z_1z_2\cdots z_i$。

考虑长度为 $i$ 的前缀 $s_i$。假设划分为 $k$ 段，每段漂亮值为 $r$。由于 $k-1$ 的划分点可能是在相同/不同数字之间，因此前 $i$ 个数字中，相邻位置不同的对数应该在 $[rk,rk+k-1]$ 之间，换句话说，确定 $k$ 之后，可能成为答案的 $r$ 也随之确定了。

我们将所有满足 $z_i\neq z_{i-1}$ 的 $i$ 保存为数列 $a_1,a_2,\cdots a_c$。枚举 $r(r\geq 1)$，$k=1$ 时，能贡献到的最短前缀显然是 $s_{a_r}$，最长前缀是 $s_{a_{r+1}-1}$。

但是 $k=2$ 的时候怎么做呢？最长前缀是 $s_{a_{2(r+1)}-1}$ 是显然的。最短前缀考虑从 $k=1$ 的情况递推过来。第一段最少截断到 $s_{a_r}$，最多截断到 $s_{a_{r+1}-1}$，因此：

对于 $k$ 更大的情况可以依次类推下去，最多枚举到 $k=\lfloor \frac{c}{r}\rfloor$ 就足够了。每次在枚举在符合要求的前缀范围执行一次区间加即可维护答案（差分一下）。另外注意一下 $r=0$ 的情况还没算，随便怎么处理下都行。

有人可能会问了，如果不同的 $r$ 对应相同的 $k$ 贡献到了同一个前缀，那答案不就算重了？这不会成为问题，因为题解的开头已经证明了对于某个前缀，当 $k$ 确定时，$r$ 不可能有多解。