记录编号	61628	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]阿狸的打字机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.498 s
提交时间	2013-06-13 14:10:28	内存使用	36.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=200000,INF=0x7fffffff;
class TTREE{//字典树
public:
	char pos;
	int father;
	bool lea;//是否叶子
	int next[30];//next[i]存的是下一位'A'+i
	TTREE(){
		pos=father=lea=0;
		for(int i=0;i<30;i++) next[i]=0;
	}
};
TTREE tt[SIZEN];
TTREE& root=tt[0];
int tot=0;
int M,N;
string str;//输入的字串
int pri[SIZEN]={0};//pri[i]表示第i个打印的字串对应的节点
int nump=0;
int fail[SIZEN]={0};//真・fail指针
class FTREE{
public:
	int father;
	vector<int> son;//子节点
};
FTREE ft[SIZEN];
int dfn[SIZEN]={0};
int low[SIZEN]={0},high[SIZEN]={0};
bool visit[SIZEN]={0};
int timer=1;
void DFS(int x){
	if(visit[x]) return;
	visit[x]=true;
	dfn[x]=timer;
	low[x]=high[x]=timer;
	timer++;
	int i;
	for(i=0;i<ft[x].son.size();i++) DFS(ft[x].son[i]);
	low[ft[x].father]=min(low[ft[x].father],low[x]);
	high[ft[x].father]=max(high[ft[x].father],high[x]);
}
void addedge(int x,int y){//x指向y,x是父节点
	ft[x].son.push_back(y);
	ft[y].father=x;
}
void singlefail(int x){
	int ch=tt[x].pos-'a';
	int temp=fail[tt[x].father];
	while(temp!=0&&tt[temp].next[ch]==0){
		temp=fail[temp];
	}
	fail[x]=tt[temp].next[ch];
	addedge(tt[temp].next[ch],x);
}
void getfail(void){
	queue<int> Q;
	int i;
	fail[0]=0;
	for(i=0;i<26;i++){
		if(root.next[i]){
			Q.push(root.next[i]);
			fail[root.next[i]]=0;
			addedge(0,root.next[i]);
		}
	}
	int x;
	while(!Q.empty()){
		x=Q.front();Q.pop();
		for(i=0;i<26;i++){
			if(tt[x].next[i]!=0){
				singlefail(tt[x].next[i]);
				Q.push(tt[x].next[i]);
			}
		}
	}
}
void addson(int x,char ch){
	if(tt[x].next[ch-'a']) return;
	tt[x].next[ch-'a']=++tot;
	tt[tot].pos=ch;
	tt[tot].father=x;
}
void maketree(void){
	int i,temp;
	temp=0;//当前访问的节点
	for(i=0;i<str.size();i++){
		if(str[i]=='B') temp=tt[temp].father;
		else if(str[i]=='P') pri[++nump]=temp;
		else{
			addson(temp,str[i]);
			temp=tt[temp].next[str[i]-'a'];
		}
	}
	N=tot+1;
	for(i=0;i<=N;i++) low[i]=INF;
}
class REQ{
public:
	int pos;
	int x,y;
};
REQ r[SIZEN];
bool operator < (REQ a,REQ b){
	return a.y<b.y;
}
void read(void){
	cin>>str;
	cin>>M;
	int i;
	for(i=1;i<=M;i++){
		scanf("%d%d",&r[i].x,&r[i].y);
		r[i].pos=i;
	}
	sort(r+1,r+1+M);
}
int sum[SIZEN]={0};//真・树状数组
int lowbit(int x){
	return x&(-x);
}
void change(int x,int num){
	while(x<=N){
		sum[x]+=num;
		x+=lowbit(x);
	}
}
int getsum(int x){
	int ans=0;
	while(x>0){
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}
int ans[SIZEN]={0};
void ask(void){
	int i,j=1,temp,nowp;
	temp=0;
	int nowr=r[1].y;
	nowp=0;
	char ch;
	for(i=0;i<str.size();i++){
		if(str[i]=='B'){
			change(dfn[temp],-1);
			temp=tt[temp].father;
		}
		else if(str[i]=='P'){
			nowp++;
			if(nowp==nowr){
				while(j<=M&&r[j].y==nowr){
					ans[r[j].pos]=getsum(high[pri[r[j].x]])-getsum(low[pri[r[j].x]]-1);
					j++;
				}
				if(j>M) break;
				nowr=r[j].y;
			}
		}
		else{
			ch=str[i];
			ch-='a';
			temp=tt[temp].next[(int)ch];
			change(dfn[temp],1);
		}
	}
	for(i=1;i<=M;i++) printf("%d\n",ans[i]);
}
int main(){
	freopen("noi2011_type.in","r",stdin);
	freopen("noi2011_type.out","w",stdout);
	read();
	maketree();
	getfail();
	DFS(0);
	ask();
	return 0;
}