题解：CF1246F Cursor Distance

· · 题解

直接做是困难的。

记 L_x,R_x 为上一个与下一个与 s_x 相同的位置。不存在则分别记为 1 和 n。

钦定一个终点 x，考虑其他点跳到 x 的步数。

对于可以一步到达 x 的点。显然，其位于 [L_x,R_x] 中。

对于可以两步到达 x 的点。其可以一步走进 [L_x,R_x] 中，然后再一步到 x。

所以可以两步到达 x 的点构成区间 [\min \limits _{i=L_x}^{R_x}L_i,\max \limits _{i=L_x}^{R_x}R_i]。

更进一步的，如果 k 步可达 x 区间是 [L,R]。则 (k+1) 步可达 x 的区间为 [\min \limits _{i=L}^{R}L_i,\max \limits _{i=L}^{R}R_i]。

一开始让 L=R=x，然后每次 L\gets \min \limits _{i=L}^{R}L_i,R \gets\max \limits _{i=L}^{R}R_i。

需要 k 步到达 x 的点会在 k 次扩展是被 [L,R] 包含。每次扩展完加上不被 [L,R] 包含的点数即可使其刚好加 k 次。即每跳一次贡献 (n-R+L-1)。

当字符串为 aaaaaaaaaa 状物时，每次扩展只能扩 1 格，所以是 \mathcal{O}(n^2) 的。

考虑优化。对于每种在 [L,R] 的同种字符，显然只有最靠左的对新的 L 有贡献，最靠右的对新的 R 有贡献。

对于相同的 L，只要区间 [L,R] 包含了某种字符，则这个字符最靠左位置固定。不难发现，如果 [L,R] 中的字符集大小不变，则 R 对 L 的扩展没有影响。右边同理。

只有 L,R 一边的情况就显然可以倍增了，跳到字符集变大的位置即可。然后在新的字符集大小重新倍增即可。

记 \lvert S \rvert=26 为字符集大小，复杂度为 \mathcal{O}(n\lvert S \rvert \log n)。