记录编号	161173	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]阿狸的打字机	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.447 s
提交时间	2015-05-02 09:13:28	内存使用	5.37 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

#define N 100010
#define MP(x,y) make_pair(x,y)
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define fir first
#define sec second

using namespace std;

void file(){
	freopen("noi2011_type.in","r",stdin);
	freopen("noi2011_type.out","w",stdout);
}

struct node{
	node *ch[26],*fail,*fa,*next[26];
	int v,id;
}*root,*pre[N];

int n,tot,sumv[N],L[N],R[N],g[N],totE,cnt,tott,ansv[N];
char S[N];
vector<pair<int,int> > ask[N];

struct edge{
	int x,to;
}E[N<<1];

queue<node*> q;

void ade(int x,int y){
	E[++totE]=(edge){y,g[x]}; g[x]=totE;
}

int qsum(int x){
	int ans=0;
	for(;x>0;x-=(x&-x)) ans+=sumv[x];
	return ans;
}

void add(int x,int v){
	for(;x<=tot;x+=(x&-x)) sumv[x]+=v;
}

void getfail(){
	q.push(root);
	while(!q.empty()){
		node* tmp=q.front(); q.pop();
		tmp->id=++tot;
		if(tmp!=root) ade(tmp->fail->id,tmp->id);
		for(int t=0;t<26;t++){
			if(tmp->ch[t]!=NULL){
				if(tmp==root) tmp->ch[t]->fail=root;
				else tmp->ch[t]->fail=tmp->fail->ch[t];
				q.push(tmp->ch[t]);
			}
			else{
				if(tmp==root) tmp->ch[t]=root;
				else tmp->ch[t]=tmp->fail->ch[t];
			}
		}
	}
}

#define p E[i].x

void dfs(int x){
	L[x]=++tott;
	for(int i=g[x];i;i=E[i].to) dfs(p);
	R[x]=tott;
}

void solve(node* x){
	add(L[x->id],1);
	for(int i=ask[x->id].size()-1;~i;i--){
		int t=ask[x->id][i].fir;
		ansv[ask[x->id][i].sec]=qsum(R[t])-qsum(L[t]-1);
	}
	for(int t=0;t<26;t++)
		if(x->next[t]!=NULL) solve(x->next[t]);
	add(L[x->id],-1);
}

int main(){
	file();
	scanf("%s",S);
	root=new node();
	node* tmp=root;
	for(int i=0,len=strlen(S);i<len;i++){
		if(S[i]=='P') pre[++cnt]=tmp;
		else if(S[i]=='B') tmp=tmp->fa;
		else{
			int t=S[i]-'a';
			if(tmp->ch[t]==NULL){
				tmp->ch[t]=new node();
				tmp->next[t]=tmp->ch[t];
			}
			tmp->ch[t]->fa=tmp;
			tmp=tmp->ch[t];
		}
	}
	getfail();
	dfs(root->id);
	scanf("%d",&n);
	for(int i=1,x,y;i<=n;i++){
		scanf("%d%d",&x,&y);
		ask[pre[y]->id].push_back(MP(pre[x]->id,i));
	}
	solve(root);
	for(int i=1;i<=n;i++)
		printf("%d\n",ansv[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}