[HDU 4787]GRE Words Revenge

操作有兩種：
1. 學一個單字
2. 讀一篇文章，問你有幾個子字串是背過的單字 (只要位置或長度不同就是不同的子字串)

如果先學完所有單字，然後給要你讀幾篇文章問你答案，可以怎麼做呢？

首先對所有單字建立$AC$自動機，然後讓每篇文章在$AC$自動機裡面轉移
每走到一個點，就把答案加上「沿著失配邊可以走到的單字結尾數量」
可以對「將所有失配邊反向形成的樹」建立樹壓平序列

把樹壓平就是對樹做一次$dfs$，把每個點的進入和離開時間記錄下來即可
這樣任何一棵子樹都可以用一個區間表示了

用線段樹來維護這個樹壓平序列
每個單字結尾相當於把整個子樹都$+1$ (實作上將樹壓平序列對應的區間$+1$)，可以使用線段樹的區間修改
「沿著失配邊可以走到的單字結尾數量」相當於樹壓平序列上對應點的值，可以使用線段樹的單點查詢
這樣讓大小$N$的$AC$自動機讀入長度$L$的文章，時間複雜度為$O(L\log N)$

現在，需要動態新增字串 (單字)
可是$AC$自動機的失配邊只能離線建立
怎麼辦呢？

解決方案：
$BIT$ ($Binary\ Indexed\ Tree$) 套$AC$自動機

當新增第$N$個字串時，$BIT$的第$N$個元素就是第$N-lowbit(N)+1$個到第$N$個字串組成的$AC$自動機
讀文章時，$BIT$查詢$\log N$個自動機把答案加起來即可

加字串到$BIT$前需要先判斷這個單字有無背過，否則會重複計算

時間複雜度：$O(10^{5}\log 10^{5}+(5*10^{6})\log^{2}10^{5})$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#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
{
    vector<vector<int> >ET,PARENT;
    vector<int>DEPTH;
    vector<pair<int,int> >SEGS;
    int N;
    void Clear(const int _N)
    {
        N=_N;
        ET.clear();
        ET.resize(N),PARENT.resize(N),DEPTH.resize(N);
        SEGS.resize(N);
    }
    void Build(const int u,const int parent,const int depth,int &tick)
    {
        DEPTH[u]=depth;
        PARENT[u].clear();
        if(parent!=-1)
        {
            for(int i=0,cur=parent;;cur=PARENT[cur][i++])
            {
                PARENT[u].push_back(cur);
                if((1<<i)>DEPTH[cur])break;
            }
        }
        SEGS[u].first=tick;
        for(int i=0;i<(int)ET[u].size();i++)Build(ET[u][i],u,depth+1,tick);
        SEGS[u].second=tick++;
    }
    SegTree SEG_TREE;
    void Build()
    {
        int tick=0;
        Build(0,-1,0,tick);
        assert(tick==N);
        SEG_TREE.Build(1,0,N-1);
    }
    int QueryLCA(int a,int b)
    {
        if(DEPTH[a]<DEPTH[b])swap(a,b);
        for(int i=0,dis=DEPTH[a]-DEPTH[b];(1<<i)<=dis;i++)if(dis&(1<<i))a=PARENT[a][i];
        assert(DEPTH[a]==DEPTH[b]);
        if(a==b)return a;
        for(int i=30;i>=0;i--)if((1<<i)<=DEPTH[a]&&PARENT[a][i]!=PARENT[b][i])
        {
            a=PARENT[a][i],b=PARENT[b][i];
        }
        assert(PARENT[a][0]==PARENT[b][0]);
        return PARENT[a][0];
    }
    void AddCount(const int u,const int count){SEG_TREE.Modify(1,0,N-1,SEGS[u].first,SEGS[u].second,count);}
    int QueryCount(const int u){return SEG_TREE.Query(1,0,N-1,SEGS[u].second);}
};
struct AC_Automaton
{
    vector<int>CH[2],COUNT;
    int N;
    void Clear()
    {
        for(int i=0;i<2;i++)CH[i].clear();
        COUNT.clear();
        N=0;Extend();
    }
    void Extend()
    {
        for(int i=0;i<2;i++)CH[i].push_back(0);
        COUNT.push_back(0);
        N++;
    }
    int GetNxt(const int u,const int c)
    {
        if(CH[c][u])return CH[c][u];
        Extend();return CH[c][u]=N-1;
    }
    bool Insert(const char *str)
    {
        int u=0;
        for(int i=0;str[i];i++)u=GetNxt(u,str[i]-'0');
        return COUNT[u]++==0;
    }
    vector<int>FAIL;
    SquashedTree TREE;
    void Build()
    {
        FAIL.resize(N);
        FAIL[0]=0;
        queue<int>q;
        for(int i=0;i<2;i++)if(CH[i][0])q.push(CH[i][0]),FAIL[CH[i][0]]=0;
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            for(int i=0;i<2;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.Clear(N);
        for(int i=1;i<N;i++)TREE.ET[FAIL[i]].push_back(i);
        TREE.Build();
        for(int i=0;i<N;i++)if(COUNT[i])TREE.AddCount(i,COUNT[i]);
    }
    long long Query(const char *str)
    {
        int u=0;
        long long ans=0;
        for(int i=0;str[i];i++)
        {
            const int c=str[i]-'0';
            while(u&&CH[c][u]==0)u=FAIL[u];
            u=CH[c][u];
            ans+=TREE.QueryCount(u);
        }
        return ans;
    }
};
struct AC_Bit
{
    AC_Automaton ACS[100001];
    string STRS[100001];
    int N;
    void Clear(){N=0;}
    void AddString(const char *str)
    {
        N++;
        STRS[N]=str;
        ACS[N].Clear();
        for(int i=N-(N&(-N))+1;i<=N;i++)ACS[N].Insert(STRS[i].c_str());
        ACS[N].Build();
    }
    long long Query(const char *str)
    {
        long long ans=0LL;
        for(int i=N;i;i-=i&(-i))ans+=ACS[i].Query(str);
        return ans;
    }
}BIT;
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    for(int n;testcount--;)
    {
        scanf("%d",&n);
        BIT.Clear();
        static int kase=1;
        printf("Case #%d:\n",kase++);
        long long ans=0LL;
        static AC_Automaton ac;
        ac.Clear();
        for(char type;n--;)
        {
            type=getchar();
            static char str0[5000001],str1[5000001];
            switch(type)
            {
                case'+':
                {
                    scanf("%s",str0);
                    int len=-1;while(str0[++len]);
                    for(int i=0;i<len;i++)str1[i]=str0[(i+ans)%len];
                    str1[len]='\0';
                    if(ac.Insert(str1))BIT.AddString(str1);
                }break;
                case'?':
                {
                    scanf("%s",str0);
                    int len=-1;while(str0[++len]);
                    for(int i=0;i<len;i++)str1[i]=str0[(i+ans)%len];
                    str1[len]='\0';
                    printf("%lld\n",ans=BIT.Query(str1));
                }break;
                default:n++;break;
            }
        }
    }
    return 0;
}