自动搬运

查看原文

来自洛谷，原作者为

	zhouhuanyi 在量子世界中，所有的未来都同样真实。

搬运于2025-08-24 22:35:06，当前版本为作者最后更新于2023-09-19 21:09:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑一个 $O(nq)$ 的暴力，令 $s_{1}=S[l_{1},r_{1}],s_{2}=S[l_{2},r_{2}]$，令 $t=\operatorname{rev}(s_{2})$，则我们仅需求 $s_{1}=A+B+C,t=\operatorname{rev}(A)+B+\operatorname{rev}(C)$ 的数量，对于每一个前缀和后缀求出其翻转是否与其相等即可，这个可以通过 $\text{kmp}$ 快速求出。

注意到翻转与自身相等的前缀为 $s_{1}+s_{2}$ 的一个 $\text{border}($后缀同理$)$，所以其也是满足 $\text{border}$ 理论的性质的，其形成了 $\log$ 段等差数列，如果使用基本子串字典模型求解出 $\log$ 段等差数列，那么如果能快速求解前缀与后缀两段等差数列之间的贡献，则可以做到 $O(q\log^2 n)$ 的复杂度。

现在快速求两段等差数列之间的贡献，考虑以下两种情况:

$1$.这两段等差数列对应的 $\text{border}$ 不交：

相当于 $s_{1}=(A+B+A+B+...+A)+E+(C+D+C+D+...+C),t=(\operatorname{rev}(A)+\operatorname{rev}(B)+\operatorname{rev}(A)+\operatorname{rev}(B)+...+\operatorname{rev}(A))+F+(\operatorname{rev}(C)+\operatorname{rev}(D)+\operatorname{rev}(C)+\operatorname{rev}(D)+...+\operatorname{rev}(C))$ 的一个形式，注意到我们统计答案时仅与 $E$ 是否 $F$ 相等，$B+A$ 是否与 $\operatorname{rev}(B)+\operatorname{rev}(A)$ 相等，$C+D$ 是否与 $\operatorname{rev}(C)+\operatorname{rev}(D)$ 相等有关，可以非常方便的统计。

$2$.这两段等差数列对应的 $\text{border}$ 有交：

比较难以处理的一部分，但可以发现必然有一个超过了一半，所以单组询问枚举的量级是 $O(\log n)$ 级别的，于是可以使用一些更加暴力的方法来维护。

判定中间的两个串相等需要一些证据的支持，但可以发现由于两段已经覆盖满了整个串，所以证据是充足的，即对于中间的两个串的每个位置两个中至少有一个可以参与判定，先将其中有一个取到最长的判掉，这部分在求出第一次使得两侧不交的位置后级可以转化为 $\text{case1}$ 的情况维护。

现在仅需考虑两侧均不取到最长的情况，容易发现判定相等的证据来源与 $A+B$ 与 $\operatorname{rev}(A)+\operatorname{rev}(B)$ 的 $\text{lcp}$ 与 $C+D$ 与 $\operatorname{rev}(C)+\operatorname{rev}(D)$ 的 $\text{lcs}$，特别的当 $A+B=\operatorname{rev}(A)+\operatorname{rev}(B)$ 与 $C+D=\operatorname{rev}(C)+\operatorname{rev}(D)$ 时其各自产生的限制是自由的，即认为时刻相等，但当这两个情况有任意一个不满足时，对应的 $\text{lcp},\text{lcs}$ 即可看作一条限制，限制中间的两个串的长度不能超过 $\text{lcp}$ 或 $\text{lcs}$。

至此我们将其转化为了纯粹的对中间的串的长度的限制，其要在 $[0,r]$ 内，那么相当于统计在两个等差序列 $A,B$ 分别取两个元素 $x,y$，$x+y\in [L,R]$ 的方案数，这个是经典类欧问题，可以做到 $O(\log n)$。

加上求解基本子串字典，复杂度为 $O(n\log^2 n+q\log^2 n)$，如果使用复杂度更小的基本子串字典可以做到 $O(n\log n+q\log^2 n)$。