题解：P16315 [ICPC 2023 Jinan R] 基本子串结构

· · 题解

不会写代码，特别是分讨。

思路

显然我们可以先把 Z 函数求出来，然后去尝试计算变化量。

考虑每个修改位置 t 产生变化后会给每个区间带来什么影响。

t 更改后 Z_i 变小了

那么会出现两种情况：

如果只有第一种情况的话，我们可以轻松地使用线段树区间改等差数列状物来计算出每个 t 更改的贡献。

考虑第二种情况，如果两个区间像上图一样不交，那么我们也可以对区间 [1,Z_i] 做刚才的操作，两者相交时，容易证明我们可以看成区间 [1,i-1] 与 [i,i+Z_i-1] 两个不交的区间做刚才的操作。

t 更改后 Z_i 变大了

本质上就是 t=Z_i+i 或者 t=Z_i+1 使得有可能 S_{Z_i+i}=S_{Z_i+1} 从而使 Z_i 增大。
此时我们需要去求增加的贡献，本质上就是求修改后 i+Z_i 与 Z_i+1 的 lcp，使用 SA 容易求得，但是需要注意当 t=Z_i+i 时，i 开头的串也可能受到修改影响。

由于字符集很大，所以要开个 map 记下所有增加贡献的字符。
从此，我们解决了此题，时间复杂度 O(n \log n)。

代码

写了 5k 有可能是我写太丑了。
存在 O(1) 的私货。