题解

思路

如果字符串集合固定，一棵 AC 自动机可以在线性时间统计集合中所有模式串在查询串里的出现次数。困难在于插入和删除会改变集合，而每次重新建立整棵自动机会退化为平方级复杂度。

把若干棵 AC 自动机按所含字符串数量做二进制分组：每组大小是二的幂，并且同一大小至多一组。插入一个字符串时先建立大小为一的组；若已有同样大小的组，就合并两组并重新建自动机，像二进制进位一样继续。每个字符串只会在每个规模层被重建一次。

做法

子任务 1：直接枚举

用集合保存当前字符串。第三类操作到来时，枚举集合中的每个模式串，并逐个起点检查它在查询串中的出现次数。相邻出现可以重叠，所以起点每次只向后移动一位。

子任务 2：只插入的二进制分组

维护若干个互不重叠的字符串组，每组建立一棵 AC 自动机。插入时按二进制进位合并等大的组。查询时分别在所有现存自动机中扫描查询串并求和。由于最多只有对数个非空组，查询复杂度只多一个对数因子。

子任务 3：加入组减去删除组

再维护第二套同样的二进制分组结构。第一类操作把字符串加入正结构；第二类操作把字符串加入负结构。第三类操作的答案等于正结构统计值减去负结构统计值。

任意字符串每次进入集合时在正结构中贡献一次，离开集合时在负结构中抵消一次。因此即使同一字符串以后再次加入，这个差值仍然恰好表示当前集合。

一棵自动机建立时，把每个模式结尾的计数沿 fail 指针从深到浅累加。扫描查询串到达某个状态时，该状态的累计计数就是所有在当前位置结尾的模式数量；对全部位置求和便得到出现次数总和。

正确性说明

每套二进制分组中的字符串组两两不交，且它们的并集正好是曾加入该结构的全部字符串实例。所以把各组 AC 自动机的查询结果相加，恰好得到这些字符串实例的总出现次数。

对任意字符串，正结构记录它被加入的次数，负结构记录它被删除的次数。题目保证操作合法，因此两者之差在字符串当前存在时为一，不存在时为零。故正结构答案减去负结构答案，恰好等于当前集合中所有字符串在查询串里的出现次数总和。

复杂度分析

设所有操作字符串总长度为 $L$。每个字符串至多参与 $O(\log m)$ 次重建，每次查询至多扫描 $O(\log m)$ 棵自动机，总时间复杂度为 $O(26L\log m)$，空间复杂度为 $O(26L)$。