Codeforces

Luogu

分析

建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。

我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。

再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,Q,vis[N]; char s[N];

int ch[N][26],fail[N],pos[N],tot=0;
void insert(char* s,int l,int id) {
    int u=0;
    for (int i=1;i<=l;++i) {
        int w=s[i]-'a';
        if (!ch[u][w]) ch[u][w]=++tot;
        u=ch[u][w];
    }
    pos[id]=u;
}
void getfail() {
    queue<int> Q;
    for (int i=0;i<26;++i) if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int i=0;i<26;++i) {
            if (ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],Q.push(ch[u][i]);
            else ch[u][i]=ch[fail[u]][i];
        }
    }
}

int c[N];
void add(int x,int y) { for (;x<=tot+1;x+=x&-x) c[x]+=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

vector<int> E[N];
int dfn[N],low[N],tim=0;
void dfs(int u) {
    dfn[u]=++tim;
    for (int v:E[u]) dfs(v);
    low[u]=tim;
}

int main() {
    Q=read(),n=read();
    for (int i=1;i<=n;++i) {
        scanf("%s",s+1); int l=strlen(s+1);
        insert(s,l,i);
    }
    getfail();
    for (int i=1;i<=tot;++i) E[fail[i]].emplace_back(i);
    dfs(0);
    for (int i=1;i<=n;++i) add(dfn[pos[i]],1),add(low[pos[i]]+1,-1),vis[i]=1;
    while (Q--) {
        char op; do op=getchar(); while (isspace(op));
        if (op=='?') {
            scanf("%s",s+1); int l=strlen(s+1); ll ans=0;
            for (int i=1,u=0;i<=l;++i)
                u=ch[u][s[i]-'a'],ans+=sum(dfn[u]);
            printf("%lld\n",ans);
        } else {
            int p=read(),u=pos[p];
            if (op=='+'&&!vis[p]) add(dfn[u],1),add(low[u]+1,-1),vis[p]=1;
            if (op=='-'&&vis[p]) add(dfn[u],-1),add(low[u]+1,1),vis[p]=0;
        }
    }
    return 0;
}