CF163E e-Government 题解

题意：

给定包含 \(k\) 个字符串的集合 \(S\)，有 \(n\) 个操作，操作有三种类型：

以 ? 开头的操作为询问操作，询问当前字符串集 \(S\) 中的每一个字符串匹配询问字符串的次数之和；

以 + 开头的操作为添加操作，表示将编号为 \(i\) 的字符串加入到集合中；

以 - 开头的操作为删除操作，表示将编号为 \(i\) 的字符串从集合中删除。

具体格式参照样例。

注意当编号为 \(i\) 的字符串已经在集合中时，允许存在添加编号为 \(i\) 的字符串的操作，但此时不执行此操作；删除亦然。

数据范围；

\(1\le n,k \le 10^5,~1\le \sum |S_i| \le 10^6\)

这题其实很简单啦，~~然后我 #define int long long 居然被卡空间了~~……

根据 Fail 树的性质，字符串 \(x\) 能对 \(y\) 有贡献，则 \(x\) 的结尾节点是 \(y\) 的某个节点的祖先。

也就是说，一个 \(x\) 能对（自己在 Fail 树上的）子树的所有节点产生 \(1\) 的贡献。

那么对于询问，我们只需要扫一遍询问串，即让一个指针在AC自动机上面跳，并统计这个节点上有多少贡献

诶，子树加，单点查询，这不就是树状数组板子吗！然后这题就做完了。

其实这道题就是 P2414 [NOI2011] 阿狸的打字机的简化版。

时间复杂度 \(\mathcal{O}\left(\left(k + \sum |S_i|\right) \log \sum |S_i|\right)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
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)(1e6 + 15))

char s[N], live[N]; ll tr[N];
vector<int> vec[N]; queue<int> q;
int tot, sz[N], dfn[N], trie[N][26], fail[N], ed[N];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= tot + 1; i += lowbit(i)) tr[i] += v; }
ll sum(int x, ll r = 0) { for(int i = x; i >= 1; i -= lowbit(i)) r += tr[i]; return r; }
void build()
{
    for(int i = 0; i < 26; i++) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i++)
            if(trie[u][i])
            {
                fail[trie[u][i]] = trie[fail[u]][i];
                q.push(trie[u][i]);
            }else { trie[u][i] = trie[fail[u]][i]; }
        vec[fail[u]].push_back(u);
    }
}
void dfs(int u)
{
    static int tim = 0; dfn[u] = ++tim; sz[u] = 1;
    for(int v : vec[u]) { dfs(v), sz[u] += sz[v]; }
}
void insert(int id)
{
    int u = 0;
    for(int i = 1; s[i]; i++)
    {
        int c = s[i] - 'a';
        if(!trie[u][c]) trie[u][c] = ++tot;
        u = trie[u][c];
    }
    ed[id] = u;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq, n; cin >> qwq >> n;
    for(int i = 1; i <= n; i++) { cin >> (s + 1); insert(i); }
    build(); dfs(0);
    for(int i = 1; i <= n; i++)
    {
        const int id = ed[i]; live[i] = true;
        add(dfn[id], 1); add(dfn[id] + sz[id], -1);
    }
    while(qwq--)
    {
        char ch; cin >> ch;
        if(ch == '?')
        {
            int p = 0; ll res = 0; cin >> (s + 1);
            for(int i = 1; s[i]; i++) {
                p = trie[p][s[i] - 'a']; res += sum(dfn[p]);
            }
            cout << res << '\n';
        }else if(ch == '-')
        {
            int id; cin >> id; if(!live[id]) continue;
            live[id] = false; id = ed[id];
            add(dfn[id], -1); add(dfn[id] + sz[id], 1);
        }else if(ch == '+')
        {
            int id; cin >> id; if(live[id]) continue;
            live[id] = true; id = ed[id];
            add(dfn[id], 1); add(dfn[id] + sz[id], -1);
        }
    }
    return 0;
}