CF587F Duff is Mad

发表于 分类于 ， ， 阅读次数：

题意：给定 个字符串 。

次询问 在 中出现次数的和。

，时限 。

给出一个非根号分治解法，复杂度只依赖于 树点数（而非总串长——叶节点深度和）。

回忆在 上是如何计算匹配次数的：对于文本串 ，将 树上到根的路径 加一；对于匹配串 ，对 树上的子树求和。

那么，问题可以转换成这样：

有 两棵树，标号对应。

每次查询将 中 到根路径 后， 中点 的子树点权的和。

可以差分，变成 的子树。即 在的子树中是的祖先是的祖先在的子树中 这就转化成，查询将 中 的子树 后， 中点 到根路径的和。

离线处理。对于询问 ,按照 的顺序回答，每次修改 的一棵子树，查询 的一条路径。

这可以使用 ，将两颗树的 序分别作为两个维度的坐标。

修改区间（子树）总数是 的。

把 重链剖分，查询的区间总数是 的。

如果直接在 两个维度上分别做，复杂度是 的，无法通过。

注意，两个维度上询问个数是不同的，我们可以调整 的划分方式来平衡复杂度（两个维度的一次询问复杂度相乘为 ）：让询问多的一维，单次复杂度为 ，询问少的一维复杂度为 。则总复杂度为 。

代码实现中，让相邻的五轮划分为 ，实际复杂度为 。

由于 的大常数，实际效率一般，最大点耗时 。