引入

CF710F

维护一个字符串集合，支持三种操作：

• 1. 加字符串
• 2. 删字符串
• 3. 查询集合中的所有字符串在给出的模板串中出现的次数

操作数 $m≤3∗10^5$，输入字符串总长度 $L≤4∗10^6$

---

如果只有第三个操作其实用 AC 自动机或者广义 SAM 都很好解决，但是它们都不支持动态插入/删除串的信息。因为维护信息必须要重构，而重构的复杂度是与插入字符串的总长有关的。不难发现信息是可以差分的，那么对于删除操作，我们可以维护一个删除信息，这样就只需要支持插入操作了。

我们可以把当前的串进行二进制拆分，即按照串的个数分成若干个组，每组有 $2^k$ 个串，每个组也有其对应的 AC 自动机。插入一个串时更新组的方法即直接模拟二进制加法即可。

一个组如果被重构，那么它的大小至少会翻一倍，因此每个串最多被重构 $\log m$ 次，而询问时只需要把串在所有组上跑一遍，则时间复杂度为 $O(L\log m)$ 。

算法简述

把需要维护的元素按照个数的二进制表示，分成不超过 $\log n$ 个组，构建每个组时进行一些预处理，使得每个组内都可以快速地询问信息。

这种方法的可扩展性其实很高，因为它有着优美的结构，把维护信息，询问信息都巧妙地均衡到了一个 $\log$ 。对于一类难以支持插入、重构复杂度高、查询效率高的数据结构问题都能适用，除了引入中提到的 AC 自动机，广义 SAM 外，凸包也是可以的。

与 zkw 线段树的联系

如果你了解 zkw 线段树的结构，你会意识到它的结构和二进制分组十分类似，二进制分组中的每个组，相当于是 zkw 线段树中的若干个节点，这些节点恰好就是区间 $[1,now]$ (我们用 $now$ 表示当前插入的元素个数) 在线段树上覆盖到的节点，在引入中的题目由于不会向下递归，因此就只保留了 $\log$ 个节点的信息。其实如果询问可能递归到下层节点的话，也是可以储存所有节点信息的，不难证明空间复杂度只会带上一个 $\log$ 。

观察二进制分组，相当于是每次在线段树中插入一个叶子节点，并把所有已经满了的父节点信息构建出来，用于询问。

这启发着我们可以做一个动态插入的线段树结构。这种结构的适用范围很广，相当于是在线构建线段树结构，维护信息的复杂度就是建树的复杂度，而且更优秀的在于它是一个支持在线的结构。

本来还有一道例题的，然而似乎我的账号被注销了，暂时没法拿到题目，所以篇幅就短了很多