CF G. Indie Album AC自动机+fail树+线段树

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500004
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct Seg {
#define lson (now<<1)
#define rson (now<<1|1)
int sum[N<<2];
void update(int l,int r,int now,int p,int v) {
sum[now]+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(p<=mid) update(l,mid,lson,p,v);
else update(mid+1,r,rson,p,v);
}
int query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) return sum[now];
int mid=(l+r)>>1,re=0;
if(L<=mid) re+=query(l,mid,lson,L,R);
if(R>mid) re+=query(mid+1,r,rson,L,R);
return re;
}
}seg;
struct Trie {
int c,to;
Trie(int c=0,int to=0):c(c),to(to){}
};
struct Node {
int ch[27];
}t[N];
struct AC {
int ch[27],f;
}a[N];
struct Q {
int i,id;
Q(int i=0,int id=0):i(i),id(id){}
};
queue<int>q;
vector<Q>G[N];
vector<Trie>T[N];
char S[N];
int n,tot,m,edges,tim,siz[N],tot2,id[N],endd[N],hd[N],nex[N],to[N],dfn[N],answer[N];
inline void add(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
inline void insert(int x) {
int rt=0,len=strlen(S+1),i;
for(i=1;i<=len;++i) {
if(!a[rt].ch[S[i]-'a']) a[rt].ch[S[i]-'a']=++tot2;
rt=a[rt].ch[S[i]-'a'];
}
endd[x]=rt;
}
inline void buildAC() {
for(int i=0;i<27;++i) if(a[0].ch[i]) q.push(a[0].ch[i]);
while(!q.empty()) {
int u=q.front(),i;
q.pop();
for(i=0;i<27;++i) {
int p=a[u].ch[i];
if(!p) {
a[u].ch[i]=a[a[u].f].ch[i];
continue;
}
a[p].f=a[a[u].f].ch[i];
q.push(p);
}
}
}
void dfs(int u) {
siz[u]=1,dfn[u]=++tim;
for(int i=hd[u];i;i=nex[i]) {
dfs(to[i]),siz[u]+=siz[to[i]];
}
}
inline void build_tree() {
int i,j;
for(i=1;i<=tot2;++i) add(a[i].f,i);
dfs(0);
}
void solve(int now,int x) {
seg.update(1,tim,1,dfn[now],1);
for(int i=0;i<G[x].size();++i) {
answer[G[x][i].i]=seg.query(1,tim,1,dfn[G[x][i].id],dfn[G[x][i].id]+siz[G[x][i].id]-1);
}
for(int i=0;i<T[x].size();++i) {
solve(a[now].ch[T[x][i].c],T[x][i].to);
}
seg.update(1,tim,1,dfn[now],-1);
}
int main() {
int i,j;
// setIO("input");
scanf("%d",&n);
for(i=1;i<=n;++i) {
int op,x,lst=0;
char str[2];
scanf("%d",&op);
if(op==2) scanf("%d",&lst),lst=id[lst];
scanf("%s",str);
if(!t[lst].ch[str[0]-'a']) {
t[lst].ch[str[0]-'a']=++tot;
id[i]=t[lst].ch[str[0]-'a'];
T[lst].push_back(Trie(str[0]-'a',id[i]));
}
else id[i]=t[lst].ch[str[0]-'a'];
}
scanf("%d",&m);
for(i=1;i<=m;++i) {
scanf("%d%s",&j,S+1),insert(i),G[id[j]].push_back(Q(i, endd[i]));
}
buildAC();
build_tree();
solve(0,0);
for(i=1;i<=m;++i) printf("%d\n",answer[i]);
return 0;
}