P11087 题解

qbf！ · 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)。