BZOJ 2434: [Noi2011]阿狸的打字机 AC自动机+fail树+线段树

#include <queue> 
#include <cstdio> 
#include <cstring>
#include <vector> 
#include <algorithm>  
#define N 300003 
#define setIO(s) freopen(s".in","r",stdin)   
using namespace std;  
struct Seg  {  
	#define lson (now<<1) 
	#define rson (now<<1|1)  
	struct Node { 
		int sum; 
	}t[N<<2]; 
	void update(int l,int r,int now,int p,int v)  {  
		t[now].sum+=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 t[now].sum; 
		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; 
	}
	#undef lson 
	#undef rson 
}seg; 
struct Node {   
	int ch[27],f,end;  
}t[N];
struct Ask { 
	int i,y; 
	Ask(int i=0,int y=0):i(i),y(y){}   
}; 
struct Graph { 
	int edges; 
	int hd[N],to[N],nex[N],fa[N],val[N]; 
	void addedge(int u,int v,int c) {
		nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;   
	}  
}trie,tree; 
queue<int>q; 
vector<Ask>G[N];   
int n,m,tot,tim,id[N],que[N],answer[N],dfn[N],size[N]; 
char op[N]; 
void buildAC() {
	int i,j; 
	for(i=0;i<27;++i) if(t[0].ch[i]) q.push(t[0].ch[i]); 
	while(!q.empty()) {
		int u=q.front();q.pop(); 
		for(i=0;i<27;++i) {
			int p=t[u].ch[i]; 
			if(!p) {
				t[u].ch[i]=t[t[u].f].ch[i]; 
				continue;  
			} 
			t[p].f=t[t[u].f].ch[i]; 
			q.push(p);   
		}
	}
} 
void dfs(int u) { 
	dfn[u]=++tim, size[u]=1; 
	for(int i=tree.hd[u];i;i=tree.nex[i]) 
		dfs(tree.to[i]), size[u]+=size[tree.to[i]];     
}
void buildtree() { 
	for(int i=1;i<=tot;++i) tree.addedge(t[i].f, i,0);      
	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].y],dfn[G[x][i].y]+size[G[x][i].y]-1);    
	for(int i=trie.hd[x];i;i=trie.nex[i]) {
		int v=trie.to[i],c=trie.val[i];  
		solve(t[now].ch[c], v);  
	}
	seg.update(1,tim,1,dfn[now],-1); 
} 
int main() {
	int i,j,lst=0,cc=0; 
	// setIO("input");              
	scanf("%s",op+1),n=strlen(op+1);
	for(i=1;i<=n;++i) {
		if(op[i]>=‘a‘&&op[i]<=‘z‘) {     
			int c=op[i]-‘a‘; 
			if(!t[lst].ch[c]) {
				t[lst].ch[c]=++tot; 
				trie.addedge(lst,tot,c); 
				trie.fa[tot]=lst;   
			}
			id[i]=lst=t[lst].ch[c];              
		}
		else { 
			if(op[i]==‘P‘) que[++cc]=i,id[i]=lst;    
			if(op[i]==‘B‘) id[i]=lst=trie.fa[lst];        
		}          
	} 
	buildAC();
	buildtree();   
	scanf("%d",&m); 
	for(i=1;i<=m;++i) {
		int x,y; 
		scanf("%d%d",&x,&y); 
		x=id[que[x]],y=id[que[y]];     
		G[y].push_back(Ask(i,x));           
	} 
	solve(0,0);   
	for(i=1;i<=m;++i) printf("%d\n",answer[i]);         
	return 0; 
}