自动搬运

查看原文

来自洛谷，原作者为

	qbf！ Never Give Up

搬运于2025-08-24 23:04:08，当前版本为作者最后更新于2025-03-31 08:54:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑用可持久化平衡树维护这个字符串的复制，这里若使用按子树大小赋权随机合并的可持久化 fhq，那么每次倍增会产生 $\mathcal O(\log^2L)$ 个结点，若使用可持久化 WBLT，合并复杂度为 $\mathcal O\left(\log\dfrac{\max(siz_x,siz_y)}{\min(siz_x,siz_y)}\right)$，则每次倍增会产生 $\mathcal O(\log L)$ 个结点，总的结点数为 $\mathcal O(\sum|w|+n\log L)$。

于是现在问题变为快速合并两个结点的信息，我们考虑维护每个结点 $x$ 所对应的字符串 $s_x$ 中，模式串 $p$ 的出现次数，以及 $s_x$ 最长的在 $p$ 中作为子串出现过的前缀和后缀（并把它们在 $p$ 中出现位置的左右端点记录下来，如有多个，随便记录一个即可）。

我们建出 $p$ 的后缀数组，合并的时候，对于最长的出现过的前缀，我们考虑二分出它在 $p$ 所有后缀中的排名。比较大小时，我们相当于要比较 $p[l_1,r_1]+p[l_2,r_2]$ 和 $p$ 的一个后缀的大小关系，只需先求出 LCP，然后比较下一位字符的大小即可。然后再求出 $p[l_1,r_1]+p[l_2,r_2]$ 与它在后缀数组中前驱后继的 LCP，较长的那个即为最长的出现过的前缀，后缀的求法是同理的，只需对反串建立后缀数组。

我们还需统计跨越合并位置的 $p$ 的出现次数，设我们合并的是 $x,y$ 两个点，则我们只需求出 $s_x$ 的一个最长后缀，使得它是 $p$ 的一个前缀，和 $s_y$ 的一个最长前缀，使得它是 $p$ 的一个后缀。

我们以 $s_y$ 为例，先二分出它在 $p$ 后缀数组中的排名，然后求出它与前驱的 LCP，设 LCP 的长度为 $len$，则我们只需求出这个前驱的最长的长度 $\le len$ 的 Border，这可以在失配树上倍增得到。

最后，设 $s_x$ 匹配 $p$ 前缀的最长后缀长度为 $l_x$，$s_y$ 能匹配 $p$ 后缀的最长前缀长度为 $l_y$，设在反串失配树上 $l_x$ 的所有祖先（含自己）构成的集合为 $A$，在正串失配树上 $l_y$ 的所有祖先（含自己）构成的集合为 $B$，则我们只需求出 $i\in A,j\in B,i+j=|p|$ 的 $(i,j)$ 对数。我们可以将所有询问离线下来，然后在正串失配树上 DFS，维护反串失配树上每个点的答案，只需支持子树加和单点查询，用树状数组维护即可。

每次合并结点时都要一个二分和树状数组的代价，都是 $\mathcal O(\log m)$ 的，故总时间复杂度为 $\mathcal O((m+\sum |w|+n\log L)\log m)$。