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。憋笑。