题解：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)$。