[bzoj2434]-[NOI2011]阿狸的打字机

题目（BZOJ）
题目（洛谷）
 
来看看这道题吧~
首先我们来想个最暴力的做法：把每个串存起来，然后暴力匹配......复杂度感人.
然后考虑加一点点优化：将这多个串放到一棵Trie上，构建AC自动机，然后像kmp那样匹配......同样感人.
我们来试试其他做法：抽离fail树。
因为在fail树上儿子节点必然可以到father结点，用树状数组维护一个dfs序即可，
具体做法就是：将询问离线，根据每个y去统计每个x，看原串：若为B，则表示退出这个结点，就把这个结点的权值-1；若为P，则表示进入这个结点，就把这个结点的权值+1。
这样就做完了，over

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=200050;
int n,m;
int c[N];
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int v){while(x<=n){c[x]+=v;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
struct querys{
	int x,y,id;
}q[N];
int ans[N];
inline bool cmp(const querys &x,const querys &y){
	return x.y<y.y;
}
struct edge{
	int vk,nxt;
}e[N<<1];
int head[N],tt,in[N],out[N],dfn[N],tim;
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
inline int idx(char c){return c-'a'+1;}
int now,cnt,ch[N][27],f[N],sz,val[N],fail[N],pos[N];
char s[N];
inline void charin(){
	n=strlen(s);int u=0;
	for(int i=0;i<n;++i){
		if(s[i]=='P'){pos[++cnt]=u;val[u]=1;continue;}
		if(s[i]=='B'){u=f[u];continue;}
		int c=idx(s[i]);
		if(!ch[u][c])ch[u][c]=++sz;
		f[ch[u][c]]=u;u=ch[u][c];
	}
}
inline void buildAC(){
	queue <int> q;
	fail[0]=0;
	for(int i=1;i<=26;++i){
		int v=ch[0][i];
		if(v)q.push(v),fail[v]=0;
	}
	while(!q.empty()){
		int r=q.front();q.pop();
		for(int i=1;i<=26;++i){
			int u=ch[r][i];
			if(!u){ch[r][i]=ch[fail[r]][i];continue;}
			q.push(u);
			int v=fail[r];
			while(v&&!ch[v][i])v=fail[v];
			fail[u]=ch[v][i];
			val[u]|=val[fail[u]];
		}
	}
}
void solve(){
	int u=0,now=0,k=1;
	for(int i=0;i<n;++i){
		switch(s[i]){
			case 'P':{
				for(now++;q[k].y==now&&k<=m;k++){
					ans[q[k].id]=query(out[pos[q[k].x]])-query(in[pos[q[k].x]]-1);
				}
				break;
			}
			case 'B':{
				change(in[u],-1);
				u=f[u];
				break;
			}
			default:{
				int c=idx(s[i]);
				u=ch[u][c];
				change(in[u],1);
				break;
			}
		}
	}
}
void dfs(int u){
	in[u]=++tim;dfn[tim]=u;
	for(int i=head[u];i;i=e[i].nxt)dfs(e[i].vk);
	out[u]=tim;
}
int main(){
	scanf("%s",s);
	read(m);
	for(int i=1;i<=m;++i){
		read(q[i].x),read(q[i].y);q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	charin();buildAC();
	for(int i=1;i<=sz;++i)ad(fail[i],i);
	dfs(0);
	solve();
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}