SA 爬了。

· · 题解

我但凡会个线性 SA，我都场切了。

考虑枚举替换的左端点 i，统计贡献。记 t_1,t_2 第一个和最后一个不相等的位置为 x,y。

然后你发现 t_1 能在 i 这个位置通过 (s_1,s_2) 换成 t_2，当且仅当 s_1=t_1[i,i+|s_1|-1] 且 s_2=t_2[i,i+|s_2|-1]，并且 i\le x 且 i+|s_1|-1\ge y。

用 SA 刻画一下子串相等的条件，我们发现如果把字符集看成二元组，令 s 表示 (s_{1,j},s_{2,j}) 构成的字符串，t 同理，那么就是要求 s=t[i,i+|s|-1]，相等于 i 这个后缀在一个排名区间内。此外还对 |s| 有一个限制。

现在相当于有 n 个点 (|s_j|,[l_j,r_j])，\mathcal{O}(L) 次询问有多少个 j 使得 |s_j|\ge y-i+1 且 \text{rk}_i\in [l_j,r_j]。按长度扫描线维护每个排名的答案，要支持区间加单点查。

先姑且我们会了线性 SA。那么如果直接上 BIT，时间复杂度是 \mathcal{O}(L\log L)，不可接受。但是你弄一个三层的分块平衡一下，时间复杂度 \mathcal{O}\left(nL^{\frac{1}{3}}+L\right)。排名区间不要用 ST 表求，改成线段树或线性 RMQ，这样不会带来 \mathcal{O}(L\log L)。

空间复杂度线性。

另外，好像写了 auto [x,y] : g，有可能 CE。憋笑。