引入

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$ 。

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

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

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

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注