50分超时：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int ch[N][26],id,cnt,a[N],ed[N],f[N],pre[N];
void ins(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
    {
    	if( s[i]>='a' && s[i]<='z')
    	{
        	int j=s[i]-'a';
        	int fa=p;
        	if(ch[p][j]==0) ch[p][j]=++id;
        	p=ch[p][j];
        	f[p]=fa;
        }
        else if(s[i]=='B') p=f[p];
        else 
        {
        	cnt++;
			a[cnt]=p;
			ed[p]=cnt;
        }
    }
}
void build()
{
    queue<int> Q;
    for(int i=0;i<26;i++)if(ch[0][i])Q.push(ch[0][i]);
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int i=0;i<26;i++)
        {
            int &y=ch[x][i];
            if(y==0)     y=ch[pre[x]][i];
            else    pre[y]=ch[pre[x]][i], Q.push(y);
        }
    }
}
int query(int x,int y)
{
	int res=0;
	int p=a[y];
	while(p)
	{
		for(int i=p;i;i=pre[i]) 
			if(ed[i]==x){ res++;break;}
		p=f[p];
	}
	return res;
}
int main()
{
	scanf("%s",s);
	id=cnt=0;memset(ch,0,sizeof(ch));
	memset(ed,0,sizeof(ed));
	ins(s);
    build();
   
    int n;scanf("%d",&n);
    while(n--)
    {
    	int x,y;scanf("%d%d",&x,&y);
    	printf("%d\n",query(x,y));
    }
    return 0;
}

70分代码超时：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int ch[N][26],id,cnt,a[N],ed[N],f[N],pre[N];
void ins(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
    {
    	if( s[i]>='a' && s[i]<='z')
    	{
        	int j=s[i]-'a';
        	int fa=p;
        	if(ch[p][j]==0) ch[p][j]=++id;
        	p=ch[p][j];
        	f[p]=fa;
        }
        else if(s[i]=='B') p=f[p];
        else 
        {
        	cnt++;
			a[cnt]=p;
			ed[p]=cnt;
        }
    }
}
void build()
{
    queue<int> Q;
    for(int i=0;i<26;i++)if(ch[0][i])Q.push(ch[0][i]);
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int i=0;i<26;i++)
        {
            int y=ch[x][i];
            if(y==0)ch[x][i]=ch[pre[x]][i];
            else    pre[y]  =ch[pre[x]][i], Q.push(y);
        }
    }
}
struct node{int x,y,id,ans;}q[N];
bool operator<(node n1,node n2){ return n1.y<n2.y;}
int sum[N],ans[N];
int query(int y)
{
	int res=0;
	int p=a[y];
	while(p)
	{
		for(int i=p;i;i=pre[i]) 
			if(ed[i])sum[ed[i]]++;
		p=f[p];
	}
	return res;
}
int main()
{
	scanf("%s",s);
	id=cnt=0;memset(ch,0,sizeof(ch));
	memset(ed,0,sizeof(ed));
	ins(s);
    build();
   
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i;
    sort(q+1,q+n+1);
    for(int i=1,j=1;i<=n;i=j)
    {
    	query(q[i].y);
    	while(q[j].y==q[i].y) q[j].ans=sum[q[j].x],j++;
    	memset(sum,0,sizeof(sum));
    }
    for(int i=1;i<=n;i++) ans[q[i].id]=q[i].ans;
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

100分代码：

#include<bits/stdc++.h>//code by cff_0102 (luogu uid 542457)
#define endl "\n"//OJ 特性 
using namespace std;
const int N=114514;
struct segmenttree{
	#define lc(x) (x<<1)
	#define rc(x) ((x<<1)|1)
	struct node{
		int l,r;
		int s;
	}a[N<<1];
	int n;
	void build(int l,int r,int p){ 
		a[p].l=l;
		a[p].r=r;
		a[p].s=0;
		int mid=(l+r)>>1;
		if(l==r)return;
		build(l,mid,lc(p));
		build(mid+1,r,rc(p));
	}
	void add(int x,int ad,int p){//把第 x 个位置的加上 ad，目前编号 p
		int l=a[p].l,r=a[p].r;
		if(l<=x&&r>=x)a[p].s+=ad;
		else return;
		if(l==r)return;
		add(x,ad,lc(p));
		add(x,ad,rc(p));
	}
	int sum(int al,int ar,int p){//问 al 到 ar 之间的和，目前编号 p
		int nl=a[p].l,nr=a[p].r;
		if(nl>=al&&nr<=ar)return a[p].s;
		if(nr<al||nl>ar)return 0;
		return sum(al,ar,lc(p))+sum(al,ar,rc(p));
	}
}st;
int ans[N];
struct query{
	int x,y,n;//n 是询问的编号
}que[N];
bool cmp(query x,query y){
	if(x.y==y.y)return x.x<y.x;
	return x.y<y.y;
}
string s;int n=0;
//AC Automaton
int tr[N][26],cnt=0,ed[N],fa[N],pre[N];
void ins(){
	int nw=0;
	for(int i=0;i<s.length();i++){
		char cc=s[i];
		if(cc>='a'){
			int c=cc-'a';
			if(tr[nw][c]==0)tr[nw][c]=++cnt,fa[tr[nw][c]]=nw;
			nw=tr[nw][c];
		}else if(cc=='P'){
			n++;
			ed[n]=nw;
		}else{
			nw=fa[nw];//回到上一个 
		}
	}
}
vector<int>e[N];//（我是一棵树）
void build(){
	queue<int>q;
	for(int i=0;i<26;i++)if(tr[0][i]){e[0].push_back(tr[0][i]),q.push(tr[0][i]);}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int y=0;y<26;y++){
			if(tr[x][y]==0)tr[x][y]=tr[pre[x]][y];
			else{
				pre[tr[x][y]]=tr[pre[x]][y];
				q.push(tr[x][y]);
				e[tr[pre[x]][y]].push_back(tr[x][y]);
			}
		}
	}
}
int dfn_=0;
int in[N],out[N];
void dfs(int x){
	in[x]=++dfn_;
	for(int y:e[x]){
		dfs(y);
	}
	out[x]=dfn_;
}//in[x] 就是点 x 的 dfn，in[x] - out[x] 就是点 x 子树的 dfn 范围
int quenow=1;//第一个还没被处理的询问的位置
int lines=0;//目前打了几行
void solve(){
	int nw=0;
	for(int i=0;i<s.length();i++){
		char cc=s[i];
		if(cc>='a'){
			int c=cc-'a';
			nw=tr[nw][c];
			st.add(in[nw],1,1);//是 in[nw]！
		}else if(cc=='B'){
			st.add(in[nw],-1,1);
			nw=fa[nw];//回到上一个
		}else{
			//看有没有要问的
			lines++;
			while(que[quenow].y==lines){
				int xyans=st.sum(in[ed[que[quenow].x]],out[ed[que[quenow].x]],1);
				ans[que[quenow].n]=xyans;
				quenow++;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>s;
	int m;cin>>m;
	for(int i=1;i<=m;i++){
		cin>>que[i].x>>que[i].y;
		que[i].n=i;
	}
	sort(que+1,que+1+m,cmp);
	ins();
	build();
	dfs(0);
	st.build(0,dfn_,1);
	solve();
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}