String Rearrangement in Phantom

先考虑一个 \(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)\)。