CF710F String Set Queries 题解

题意：

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

加字符串

删字符串

查询集合中的所有字符串在给出的模板串中出现的次数

操作数 \(m \leq 3 \times 10^5\)，输入字符串总长度 \(\sum |s_i| \leq 3\times 10^5\)。

本题强制在线，应该在每次输出后调用fflush(stdout)。

你只有在输出上一个询问的答案后才能读入下一组询问。

过了好几天了才开始写题解，着实有些懒。（最近两只手都腱鞘炎了）

这道题就是二进制分组 + AC 自动机，下面我们来分析这个想法是怎么来的。

先考虑暴力，我们每次删除的时候都对原字符串进行重构，显然这是一种低效的方式。

这个其实很好解决。由于贡献是可以加减的，所以我们考虑把删除操作改为在另一个 Trie 上面插字符串

我们称原先的 Trie 是 Add 树，另外的是 Sub 树，那么答案就是 Add 树的贡献减 Sub 树的贡献。

思考一下这样的时间复杂度是多少：最坏情况下，字符长度一定为 \(1,2,3,\cdots,k\) ，且 \(k \le \sqrt{2\,\mathrm{len}}\) ，

其中 \(\mathrm{len} = \sum|s_i|\) ，故不做其他优化的话，时间复杂度是 \(\mathcal{O}(\mathrm{len}^2)\) 。

于是接下来就有两种处理方法：

第一种，我们只需要枚举集合中比当前串长度小的串即可，此时时间复杂度是 \(\mathcal{O}(\mathrm{len}\sqrt{\mathrm{len}})\)
第二种，也就是我们前面提到的二进制分组。

第一种方法确实是很妙，如果没懂可以参考这篇文章，不过本文要讲第二种方法。

我们考虑对每次插入，都新建一个 Trie ，记它的大小为 \(1\) ，那么我们要维护形如 \(1,2,4,8,16,\cdots\) 若干棵 Trie

什么意思呢？比如我们现在有大小为 \(1,2,8\) 三棵 Trie ，此时的操作是插入，我们新建了一个大小为 \(1\) 的 Trie

此时我们有 \(1,1,2,8\) 四棵 Trie ，然后我们直接把相同大小的合并，就像游戏 2048 一样，最终得到 \(4,8\) 两棵 Trie

考虑这样的操作对复杂度有什么影响：

每次合并，就是把构造其中一棵树的所有字符串插到另一棵里，然后删掉这棵树。

而 AC 自动机的构造过程是线性的，因此时间复杂度为 \(\mathcal{O}(\mathrm{len}\log n)\) 。

写的好看一点，就是 \(\mathcal{O}(\sum|s_i|\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

struct Trie
{
    string data[N];
    int n, tot, ch[N][26], ed[N], fail[N];
    void insert(int rt, char *s)
    {
        int u = rt, len = strlen(s + 1);
        for(int i = 1; i <= len; i++)
        {
            int c = s[i] - 'a';
            if(ch[u][c] == rt) {
                ch[u][c] = ++tot;
                for(int j = 0; j < 26; j++) ch[tot][j] = rt;
            }
            u = ch[u][c];
        }
        ++ed[u];
    }
    void build(int rt)
    {
        fail[rt] = rt; queue<int> q;
        for(int i = 0; i < 26; i++)
            if(ch[rt][i] > rt) { q.push(ch[rt][i]), fail[ch[rt][i]] = rt; }
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int i = 0; i < 26; i++)
            {
                if(ch[u][i] != rt)
                {
                    fail[ch[u][i]] = ch[fail[u]][i];
                    ed[ch[u][i]] += ed[ch[fail[u]][i]]; q.push(ch[u][i]);
                }
                else ch[u][i] = ch[fail[u]][i];
            }
        }
    }
    int search(int u, char *s)
    {
        int res = 0, len = strlen(s + 1);
        for(int i = 1; i <= len; i++)
        {
            int c = s[i] - 'a';
            u = ch[u][c]; res += ed[u];
        }
        return res;
    }
    int top,stk[N],fr[N],sz[N];
    void merge()
    {
        --top; sz[top] *= 2;
        for(int i = stk[top]; i <= tot; i++)
        {
            ed[i] = fail[i] = 0;
            for(int j = 0; j < 26; j++) ch[i][j] = 0;
        }
        tot = stk[top];
        for(int i = 0; i < 26; i++) ch[tot][i] = tot;
        for(int L = fr[top]; L <= n; L++) insert(stk[top], &data[L][0]);
        build(stk[top]);
    }
    void Ins(char *s)
    {
        stk[++top] = ++tot;
        for(int i = 0; i < 26; i++) ch[tot][i] = tot;
        sz[top] = 1; insert(tot, s); build(stk[top]);
        int len = strlen(s + 1); data[fr[top] = ++n] = " ";
        for(int i = 1; i <= len; i++) data[n] += s[i];
        while(sz[top] == sz[top - 1]) merge();
    }
    int Count(char *s)
    {
        int res = 0;
        for(int i = 1; i <= top; i++)
            res += search(stk[i], s);
        return res;
    }
}Add, Sub;
char tmp[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; for(cin >> Q; Q--; )
    {
        int op; cin >> op >> (tmp + 1);
        if(op == 1) Add.Ins(tmp); else if (op == 2) Sub.Ins(tmp);
        else cout << Add.Count(tmp) - Sub.Count(tmp) << '\n'; cout.flush();
    }
    return 0;
}