[Codeforces 163E]e-Government

這題給你一個字串集合$\{A_{i}\}$ ($1\leq i\leq N$)
然後是$Q$個操作，分為三種
1. 將$A_{i}$從集合中移除
2. 將$A_{i}$加回集合中
3. 給你字串$S$，問你$S$中可以數出幾個$\{A_{i}\}$的元素？
例如$\{A_{i}\}=\{"a","aa","aaa"\}$，$S="aaaa"$，你應該回答$9$

我們可以先把$\{A_{i}\}$建成$AC$自動機，然後讓$S$在裡面進行轉移
每走一個點，就將沿著失配邊可以走到的所有單字結尾的計數器都$+1$
走完時，每個單字結尾的計數器數值加起來就是答案了

當然，真的這麼做會TLE，每走一步就沿失配邊遍歷每個可以走到的單字結尾實在太花時間了

可以發現，將所有的失配邊反向可以形成一棵根節點為$0$的樹
於是我們就可以建立這棵樹的壓扁序列，這樣每棵子樹就都能剛好對應到一個區間了

那要怎麼做到快速的將沿著失配邊可以走到的所有單字結尾的計數器都$+1$呢？
反向思考，為甚麼我們不先把所有點的$+1$次數都算好？

於是，我們可以將每個以單字結尾為根的子樹全部$+1$
可以透過用線段樹維護樹壓扁序列，實現區間修改來達成

於是，要怎麼取得某個節點沿著失配邊走會遇到幾個單字結尾呢？
就是線段樹的單點查詢啦！

於是操作3.我們可以做到時間複雜度$O(\left|S\right|\log(\sum_{i=1}^{N}\left|A_{i}\right|))$！

那麼操作1.和2.呢？
移除單字相當於將以對應的單字結尾為根的子樹裡的每個點全部$-1$
那麼加回單字當然就是將子樹裡的每個點全部$+1$了
將樹壓扁序列對應的區間做適當的區間修改即可
時間複雜度$O(\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

總時間複雜度：$O(\sum_{i=1}^{N}\left|A_{i}\right|+(\sum S)\log(\sum_{i=1}^{N}\left|A_{i}\right|)+Q\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
struct SegTree
{
    vector<int>S;
    void Build(const int id,const int l,const int r)
    {
        while((int)S.size()<=id)S.push_back(0);
        S[id]=0;
        if(l<r)
        {
            const int mid=(l+r)/2;
            Build(id*2,l,mid),Build(id*2+1,mid+1,r);
        }
    }
    void Modify(const int id,const int l,const int r,const int bl,const int br,const int val)
    {
        if(r<bl||br<l)return;
        if(bl<=l&&r<=br){S[id]+=val;return;}
        const int mid=(l+r)/2;
        Modify(id*2,l,mid,bl,br,val),Modify(id*2+1,mid+1,r,bl,br,val);
    }
    int Query(const int id,const int l,const int r,const int loc)
    {
        if(l==r)return S[id];
        const int mid=(l+r)/2;
        if(loc<=mid)return S[id]+Query(id*2,l,mid,loc);
        else return S[id]+Query(id*2+1,mid+1,r,loc);
    }
};
struct SquashedTree
{
    SegTree SEG_TREE;
    vector<vector<int> >ET;
    vector<pair<int,int> >SEGMENTS;
    int N;
    void Clear(const int _N){N=_N;ET.clear();ET.resize(N),SEGMENTS.resize(N);}
    void Build(const int u,int &tick)
    {
        SEGMENTS[u].first=tick;
        for(const int nxt:ET[u])Build(nxt,tick);
        SEGMENTS[u].second=tick++;
    }
    void Build()
    {
        int tick=0;
        Build(0,tick);
        assert(tick==N);
        SEG_TREE.Build(1,0,N-1);
    }
    void ModifyNode(const int u,const int val)
    {
        SEG_TREE.Modify(1,0,N-1,SEGMENTS[u].first,SEGMENTS[u].second,val);
    }
    int QueryParentsSum(const int u)
    {
        return SEG_TREE.Query(1,0,N-1,SEGMENTS[u].second);
    }
};
struct AC_Automaton
{
    vector<int>CH[26],CITIZENS;
    vector<bool>INCLUDED;
    int SZ;
    void Clear()
    {
        for(int i=0;i<26;i++)CH[i].clear();
        CITIZENS.clear(),INCLUDED.clear();
        SZ=0;
        Expand();
    }
    void Expand()
    {
        for(int i=0;i<26;i++)CH[i].push_back(0);
        SZ++;
    }
    int GetNxt(const int u,const int c)
    {
        if(CH[c][u])return CH[c][u];
        Expand();
        return CH[c][u]=SZ-1;
    }
    void Insert(const char *str)
    {
        int u=0;
        for(int i=0;str[i];i++)u=GetNxt(u,str[i]-'a');
        CITIZENS.push_back(u);
        INCLUDED.push_back(false);
    }
    vector<int>FAIL;
    SquashedTree TREE;
    void BuildFail()
    {
        FAIL.resize(SZ);
        TREE.Clear(SZ);
        FAIL[0]=0;
        queue<int>q;
        for(int i=0;i<26;i++)if(CH[i][0])FAIL[CH[i][0]]=0,q.push(CH[i][0]),TREE.ET[0].push_back(CH[i][0]);
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            for(int i=0;i<26;i++)if(CH[i][u])
            {
                int &f=FAIL[CH[i][u]]=FAIL[u];
                while(f&&CH[i][f]==0)f=FAIL[f];
                f=CH[i][f];
                q.push(CH[i][u]),TREE.ET[f].push_back(CH[i][u]);
            }
        }
        TREE.Build();
        for(int i=0;i<(int)CITIZENS.size();i++)ModifyCitizen(i,1);
    }
    void ModifyCitizen(const int id,const int val)
    {
        if(val==1){if(INCLUDED[id])return;INCLUDED[id]=true;}
        else if(val==-1){if(!INCLUDED[id])return;INCLUDED[id]=false;}
        else assert(0);
        TREE.ModifyNode(CITIZENS[id],val);
    }
    long long ReadText(const char *str)
    {
        long long ans=0LL;
        int u=0;
        for(int i=0;str[i];i++)
        {
            const int c=str[i]-'a';
            while(u&&CH[c][u]==0)u=FAIL[u];
            u=CH[c][u];
            ans+=TREE.QueryParentsSum(u);
        }
        return ans;
    }
}AC;
int N;
char S[1000001];
int main()
{
//    freopen("in.txt","r",stdin);
    int querycount;scanf("%d%d",&querycount,&N);
    AC.Clear();
    for(int i=0;i<N;i++)
    {
        scanf("%s",S);
        AC.Insert(S);
    }
    AC.BuildFail();
    for(char type;querycount--;)
    {
        index_reinput:;
        type=getchar();
        switch(type)
        {
            case'+':
            {
                int id;scanf("%d",&id),id--;
                AC.ModifyCitizen(id,1);
            }break;
            case'-':
            {
                int id;scanf("%d",&id),id--;
                AC.ModifyCitizen(id,-1);
            }break;
            case'?':
            {
                scanf("%s",S);
                printf("%lld\n",AC.ReadText(S));
            }break;
            default:goto index_reinput;
        }
    }
    return 0;
}