CF G. Indie Album 广义后缀自动机+树链剖分+线段树合并

#include <map>
#include <vector> 
#include <queue> 
#include <cstdio>  
#include <cstring> 
#include <algorithm>
#define N 400003 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;  
char S[N]; 
int n,m,rt[N<<1];   
namespace Trie {
	int id[N],tim; 
	struct Node {    
		map<int,int>ch;   
		int siz,dfn,top,son,fa;     
	}t[N];  
	void dfs1(int u) { 
		t[u].siz=1; 
		for(int i=0;i<27;++i) 
			if(t[u].ch.count(i)) {    
				int v=t[u].ch[i]; 
				t[v].fa=u,dfs1(v),t[u].siz+=t[v].siz;   
				if(!t[u].son||t[v].siz>t[t[u].son].siz) t[u].son=v;    
			}
	} 
	void dfs2(int u,int tp) {
		t[u].top=tp; 
		t[u].dfn=++tim;   
		if(t[u].son) dfs2(t[u].son,tp); 
		for(int i=0;i<27;++i) 
			if(t[u].ch.count(i)) { 
				int v=t[u].ch[i]; 
				if(v!=t[u].son) 
					dfs2(v,v); 
			} 
	}
	void build_tree() {  
		dfs1(0), dfs2(0,0);    
	}
}; 
namespace seg { 
	#define ls t[x].lson 
	#define rs t[x].rson
	int tot; 
	struct Node { 
		int lson,rson,sum; 
	}t[N*50]; 
	void pushup(int x) {
		t[x].sum=t[ls].sum+t[rs].sum;    
	}
	void update(int &x,int l,int r,int p,int v) {
		if(!x) 
			x=++tot; 
		if(l==r) {
			t[x].sum=v; 
			return;
		} 
		int mid=(l+r)>>1;    
		if(p<=mid) update(ls,l,mid,p,v); 
		else update(rs,mid+1,r,p,v); 
		pushup(x);  
	}
	int query(int x,int l,int r,int L,int R) {
		if(!x) return 0; 
		if(l>=L&&r<=R) return t[x].sum; 
		int mid=(l+r)>>1,re=0; 
		if(L<=mid) re+=query(ls,l,mid,L,R); 
		if(R>mid) re+=query(rs,mid+1,r,L,R);  
		return re; 
	}
	int merge(int l,int r,int x,int y,int tt) { 
		if(!x||!y) 
			return x+y;  
		int oo=++tot;      
		if(l==r) 
			t[oo].sum=1;                 
		else { 
			int mid=(l+r)>>1; 
			t[oo].lson=merge(l,mid,t[x].lson,t[y].lson,tt); 
			t[oo].rson=merge(mid+1,r,t[x].rson,t[y].rson,tt); 
			pushup(oo);   
		} 
		return oo; 
	}
	#undef ls
	#undef rs
}; 
namespace SAM {  
	int tot,id[N<<1],tax[N<<1],rk[N<<1];      
	struct Node {  
		map<int,int>ch; 
		int len,pre; 
	}t[N<<1];            
	struct Edge { 
		int from,c;      
		Edge(int from=0,int c=0):from(from),c(c){} 
	};             
	queue<int>q; 
	int extend(int lst,int c,int i) {      
		int p=lst; 
	    if(t[p].ch.count(c)) { 
	    	int q=t[p].ch[c]; 
	    	if(t[q].len==t[p].len+1) seg::update(rt[q],1,Trie::tim,i,1),lst=q; 
	    	else { 
	    		int nq=++tot; 
	    		t[nq].len=t[p].len+1;  
	    		t[nq].pre=t[q].pre,t[q].pre=nq;     
	    		t[nq].ch=t[q].ch; 
	    		seg::update(rt[nq],1,Trie::tim,i,1);      
	    		for(;p&&t[p].ch.count(c)&&t[p].ch[c]==q;p=t[p].pre) t[p].ch[c]=nq;      
	    		lst=nq;            
	    	}
	    } 
	    else { 
	    	int np=++tot;  
	    	t[np].len=t[p].len+1;  
	    	seg::update(rt[np],1,Trie::tim,i,1);    
	    	for(;p&&!t[p].ch.count(c);p=t[p].pre) t[p].ch[c]=np;   
	    	if(!p) t[np].pre=1;  
	        else {
	        	int q=t[p].ch[c]; 
	        	if(t[q].len==t[p].len+1) t[np].pre=q;     
	        	else { 
	        		int nq=++tot; 
	        		t[nq].len=t[p].len+1; 
	        		t[nq].pre=t[q].pre,t[q].pre=t[np].pre=nq;         
	        		t[nq].ch=t[q].ch; 
	        		for(;p&&t[p].ch.count(c)&&t[p].ch[c]==q;p=t[p].pre) t[p].ch[c]=nq;  
	        	}
	        }
	        lst=np; 
	    }  
	    return lst;  
	}  
	void construct() {
		int i,j; 
		id[0]=tot=1;   
		q.push(0);    
		while(!q.empty()) {
			int u=q.front();q.pop(); 
			for(i=0;i<27;++i) {
				if(Trie::t[u].ch.count(i)) { 
					int v=Trie::t[u].ch[i];   
					q.push(v);               
					id[v]=extend(id[u],i,Trie::t[v].dfn);        
				}
			}
		} 
		for(i=1;i<=tot;++i) tax[i]=0; 
		for(i=1;i<=tot;++i) ++tax[t[i].len];    
		for(i=1;i<=tot;++i) tax[i]+=tax[i-1];        
		for(i=1;i<=tot;++i) rk[tax[t[i].len]--]=i;   
		for(i=tot;i>1;--i) { 
			int u=rk[i];     
			int ff=t[u].pre;   
			if(ff>1) 
				rt[ff]=seg::merge(1,Trie::tim,rt[u],rt[ff],0); 
		}
	} 
}; 
void solve(int x) { 
	int p=1,i,len=strlen(S+1),re=0; 
	for(i=1;i<=len;++i) {
		int c=S[i]-‘a‘; 
		if(SAM::t[p].ch.count(c)) 
			p=SAM::t[p].ch[c]; 
		else {
			printf("0\n"); 
			return; 
		}
	}    
	for(x=Trie::id[x];x;x=Trie::t[Trie::t[x].top].fa) {  
	    re+=seg::query(rt[p],1,Trie::tim,Trie::t[Trie::t[x].top].dfn,Trie::t[x].dfn);       
	}
	printf("%d\n",re);     
}
int main() {
	int i,j; 
	// setIO("input"); 
	scanf("%d",&n); 
	for(i=1;i<=n;++i) {
		int op,lst=0; 
		char str[3];  
		scanf("%d",&op);      
		if(op==2) scanf("%d",&lst),lst=Trie::id[lst]; 
		scanf("%s",str);   
		if(!Trie::t[lst].ch.count(str[0]-‘a‘)) {  
			Trie::t[lst].ch[str[0]-‘a‘]=i; 
			Trie::id[i]=i;        
		}
		else Trie::id[i]=Trie::t[lst].ch[str[0]-‘a‘];   
	} 
	Trie::build_tree();   
	SAM::construct();     
	scanf("%d",&m);   
	for(i=1;i<=m;++i) 
		scanf("%d%s",&j,S+1), solve(j);       
	return 0; 
}