CF1286E Fedya the Potter Strikes Back

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

题意：维护字符串 和序列 ，初始为空。

次操作，第 次操作在 末尾添加字符 ，在序列 末尾添加数字 。

定义一个子区间 的可疑度为：

  • 子串 和前缀 相同：其可疑度为 。
  • 否则：可疑度为 。

每次操作后，求出当前的串的所有子区间的可疑度之和。

强制在线，。

题意等价于动态 并维护 权值和。

用 KMP 逐位求出 数组。

加入字符 时，若直接枚举新增的 ，复杂度太高。

考虑 的 相比 的变化：

  • 对于原有的 ：
    • 若新字符失配，则消失；
    • 若新字符匹配，则长度加一。
  • 若 则新增一个长度为 的 。

显然 的新增和删除都是 次。如何快速找到该删除的 ？

记节点 对应前缀的下一个字符为 。在 树上，记节点 最近的， 不同的祖先为 。（容易维护）

需要删除的节点即为 到根的链上 的点。可以从 向上一路跳跃，利用 批量跳过 的不用删的点。

接下来需要维护 的权值和：对于未删除的 ，权值都需要对 取 。

只需这样的一个数据结构：支持删除，插入，全体取 ，求和。

用 std::map 维护每个权值及其出现次数，暴力取 ，复杂度均摊正确。

删除某个 时需要获知其权值，这可以使用 ST 表来得到。

总复杂度 。