BZOJ_3881_[Coci2015]Divljak_AC自动机+dfs序+树状数组

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc() {
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
    int x=0;char c=nc();
    while(c<‘0‘||c>‘9‘) c=nc();
    while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-‘0‘,c=nc();
    return x;
}
#define N 2000050
#define M 100050
int fail[N],ch[N][26],xx[M],yy[M],n,idx,cnt=1,pos[M],Q[N],l,r,head[N],to[N],nxt[N],c[N],dfn[N],son[N],a[N],m;
int f[22][N],dep[N];
bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}
inline void add(int u,int v) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void fix(int x,int v) {
    for(;x<=dfn[0];x+=x&(-x)) c[x]+=v;
}
int inq(int x) {
    int re=0; 
    for(;x;x-=x&(-x)) re+=c[x];
    return re;
}
void build_ac() {
    int i,p;
    for(i=0;i<26;i++) ch[0][i]=1;
    Q[r++]=1;
    while(l<r) {
        p=Q[l++];
        for(i=0;i<26;i++) {
            if(ch[p][i]) fail[ch[p][i]]=ch[fail[p]][i],Q[r++]=ch[p][i];
            else ch[p][i]=ch[fail[p]][i];
        }
    }
}
void dfs(int x) {
    int i; 
    dfn[x]=++dfn[0];
    for(i=head[x];i;i=nxt[i]) {
        f[0][to[i]]=x; dep[to[i]]=dep[x]+1;
        dfs(to[i]);
    }
    son[x]=dfn[0];
}
int lca(int x,int y) {
    int i;
    if(dep[x]<dep[y]) swap(x,y);
    for(i=21;i>=0;i--) {
        if(dep[f[i][x]]>=dep[y]) x=f[i][x];
    }
    if(x==y) return x;
    for(i=21;i>=0;i--) {
        if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
    }
    return f[0][x];
}
int main() {
    n=rd();
    int i,j,x;
    for(i=1;i<=n;i++) {
        char s=nc(); int p=1;
        while(s<‘a‘||s>‘z‘) s=nc();
        for(;s>=‘a‘&&s<=‘z‘;s=nc()) {
            int &k=ch[p][s-‘a‘];
            if(!k) k=++cnt;
            p=k;
        }
        pos[i]=p;
    }
    int tot=cnt; cnt=0;
    build_ac();
    for(i=1;i<=tot;i++) if(fail[i]) add(fail[i],i);
    dfs(1);
    for(i=1;(1<<i)<=tot;i++) {
        for(j=1;j<=tot;j++) {
            f[i][j]=f[i-1][f[i-1][j]];
        }
    }
    m=rd();
    int opt;
    while(m--) {
        opt=rd();
        if(opt==1) {
            a[0]=0;
            char s=nc(); int p=1;
            while(s<‘a‘||s>‘z‘) s=nc();
            for(;s>=‘a‘&&s<=‘z‘;s=nc()) {
                p=ch[p][s-‘a‘];
                a[++a[0]]=p; fix(dfn[p],1);
            }
            sort(a+1,a+a[0]+1,cmp);
            for(i=1;i<a[0];i++) {
                fix(dfn[lca(a[i],a[i+1])],-1);
            }
        }else {
            x=rd();
            int p=pos[x];
            printf("%d\n",inq(son[p])-inq(dfn[p]-1));
        }
    }
}