P9997 [Ynoi2000] pmpkmp

· · 题解

*P9997 [Ynoi2000] pmpkmp

询问离线，所有询问串已知。可以预见做法需要线性求文本串的每相邻 X 个字符能匹配哪个询问串，对此最简单的结构是 AC 自动机。对所有询问串建出 AC 自动机。所有询问串等长，将文本串放在自动机上跑，可以求出所有出现的询问串以及它们的出现位置。

维护每个点向上跳 X 步对应的字符串，修改时涉及不可接受数量的结点，不可取。考虑树上结构，结合链修改链查询容易想到树剖。于是树上路径分成若干部分，每一部分是一段连续的重链，称为子路径。

查询的贡献分成两部分：完全出现在某个重链上的询问串；从某条重链开始，但跨过多个重链的询问串。

第二部分的贡献容易统计。取每段子路径最后的 X - 1 个字符以及路径上接下来的 X 个字符（注意不是 X - 1 个，因为字符串可以从子路径的最后一个点开始而不取子路径的任何字符，调了好久）与询问串做匹配，总复杂度 \mathcal{O}(mX\log n)。

对于第一部分，维护每条重链的每个在重链上深度大于 X（保证不跳出重链，这样重链之间才独立）的点向上跳 X 步对应的字符串。区间查询权值为 v 的数的个数，其中 v 的值域是 m（最后会知道是 2m），因为 AC 自动机建立了询问串到 1\sim m 的映射。

修改即对每条子路径暴力更新被修改的部分加上前后各 X - 1 个字符的信息。单点修改，区间查询权值为 v 的数的个数。类二维数点，因修改和查询均可离线，对每个权值分别做，BIT 即可。查询的第一部分的复杂度为 \mathcal{O}(C\log n)，其中 C 是子路径数总和，显然不超过 mX。

修改的复杂度看似是 \mathcal{O}(mX\min(X, \log n)\log n)，即每条子路径贡献 X，而子路径数不超过 m\min(X, \log n)。但由于除了一条子路径以外的所有子路径均处于重链顶端，此时 “上方 X - 1 个字符” 不存在，因此若这样的子路径长度为 l，则修改只涉及 l + X 个结点，于是单点修改的次数不超过 l，这些子路径贡献的单点修改次数总和为 \sum l = X，而涉及到的结点个数总和为 \sum (l + X) = \mathcal{O}(X\log n)，后者匹配的是 AC 自动机线性复杂度。

总复杂度 \mathcal{O}(n + mX\log n)。要代码对拍之类的可以私信。

本题细节颇多，主要几点：

  1. 注意忽略 x, y 的 LCA 到它父亲的字符。即修改涉及到的字符为 x 到 y 的除了 LCA 以外的所有点到它父亲的字符，按顺序。
  2. 路径有序，要么向上 X 个字符和它的逆序都维护，要么往 AC 自动机加入询问串的反串。肯定选后者，因为前者的两倍常数乘在了单点修改且常数较大的 mX\log n 上，而后者的两倍常数仅仅扩大了 AC 自动机的规模，乘在线性的 mX |\Sigma| 上。
  3. 处理路径方向，确定深度较大的结点（取出字符）一定要万分细心。

算是一道不错的练手题，思维含量不高。好在不卡常。