记录编号	380694	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]阿狸的打字机	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2017-03-09 21:45:30	内存使用	16.03 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
const int maxn=100005;
struct Rabit_tree{int to,next;}e[maxn];
int ln,cnt=0,n=0,cot=0,ch[maxn][26],fail[maxn],pos[maxn],fa[maxn];
int q[maxn],head[maxn],len=1,dfn[maxn],en[maxn],ans[maxn];char o[maxn];
int low[maxn],c[maxn];
void R_add(int i,int x){
	for(;i<=cot;i+=low[i])c[i]+=x;
}
int R_get(int p){
	int i,res=0;
	for(i=dfn[p]-1;i;i-=low[i])res-=c[i];
	for(i=en[p];i;i-=low[i])res+=c[i];
	return res;
}
void Rabit_set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
void Rabit_in(){
	scanf("%s",o);
	int p=0,i,x;ln=strlen(o);
	for(i=0;i<ln;i++)
		if(o[i]=='P')pos[++n]=p;
		else if(o[i]=='B')p=fa[p];
		else {
			x=o[i]-'a';
			if(!ch[p][x])ch[p][x]=++cnt,fa[cnt]=p;
			p=ch[p][x];
		}
}
void Dig(){
	int s=1,t=0,rt,i,x,u;
	for(i=0;i<26;i++)if(ch[0][i])q[++t]=ch[0][i];
	while(s<=t){
		rt=q[s++];
		for(i=0;i<26;i++){
			u=ch[rt][i];
			if(!u){ch[rt][i]=ch[fail[rt]][i];continue;}
			q[++t]=u;x=fail[rt];
			while(x&&!ch[x][i])x=fail[x];
			x=ch[x][i];fail[u]=x;
		}
	}
	for(i=1;i<=cnt;i++)Rabit_set(fail[i],i);
}
void Dfs(int rt){
	dfn[rt]=++cot;
	for(int i=head[rt];i;i=e[i].next)
		if(!dfn[e[i].to])Dfs(e[i].to);
	en[rt]=cot;
}
struct QUE {
	int x,y,num;
	bool operator < (const QUE &a)const{
		return y<a.y;
	}
}Que[maxn];
void Rabit_ans(){
	int m,x,y,p=0,i,j=0;R_int(m);Dig();Dfs(0);
	for(i=1;i<=cot;i++)low[i]=i&(-i);
	for(i=0;i<m;i++)R_int(Que[i].x),R_int(Que[i].y),Que[i].num=i;
	sort(Que,Que+m);n=0;
	for(i=0;i<ln;i++)
		if(o[i]=='P'){
			n++;while(Que[j].y==n)ans[Que[j].num]=R_get(pos[Que[j].x]),j++;
		}
		else if(o[i]=='B')R_add(dfn[p],-1),p=fa[p];
		else p=ch[p][o[i]-'a'],R_add(dfn[p],1);
	for(i=0;i<m;i++)printf("%d\n",ans[i]);
}
int main(){
	freopen("noi2011_type.in","r",stdin);freopen("noi2011_type.out","w",stdout);
	Rabit_in();Rabit_ans();
}