这一题总算是过了..然而在某OJ上还是给70分可能是递归的栈爆炸了吧?

感谢@bx2k @billxu2000 提供解法思路

首先题面显著的告诉你:给你个trie

所以你把trie的fail指针求出来,这里面是AC自动机的求法

然后我们把询问给离线出来

然后..trie的fail是一颗树,我们可以把这颗树拿出来

每次我们询问对root到y的trie树路径上权值改为1其他为0的情况下,求x所在的fail树内的权值和即可

所以代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[100005];
struct node
{
    int id;
    node * father;
    node * fail;
    node * ch[26];
    node ()
    {
        father=0;
        fail=0;
        memset(ch,0,sizeof(ch));
    }
};
node * b[100005];
node * root;
node * new_node()
{
    static node a[100005];
    static int top=0;
    return &a[top++];
}
struct edge
{
    int y;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
void insert_edge(int x,int y)
{
    edge * t = new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
int dfn[100005];
int size[100005];
void dfs(int x)
{
    static int now=0;
    dfn[x]=now++;
    edge * t;
    size[x]=1;
    for (t=li[x];t!=0;t=t->next)
    {
        dfs(t->y);
        size[x]+=size[t->y];
    }
}
struct query
{
    int id;
    int x;
    int y;
    friend bool operator < (const query &a,const query &b)
    {
        return a.y<b.y;
    }
    void read()
    {
        scanf("%d%d",&x,&y);
        x--;
        y--;
    }
};
query c[100005];
int val[1<<18];
int querys(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    int sum=0;
    if (l0<mid) sum+=querys(num*2+1,l,mid,l0,r0);
    if (mid<r0) sum+=querys(num*2+2,mid,r,l0,r0);
    return sum;
}
void change(int num,int l,int r,int k,int t)
{
    if (l==r-1)
    {
        val[num]=t;
        return;
    }
    int mid=(l+r)/2;
    if (k<mid)
    {
        change(num*2+1,l,mid,k,t);
    }
    else
    {
        change(num*2+2,mid,r,k,t);
    }
    val[num]=val[num*2+1]+val[num*2+2];
}
int ans[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%s",a);
    root=new_node();
    node * now=root;
    int i;
    int sum=0;
    for (i=0;a[i]!='\0';i++)
    {
        if (a[i]=='P')
        {
            b[sum++]=now;
        }
        else if (a[i]=='B')
        {
            now=now->father;
        }
        else
        {
            if (now->ch[a[i]-'a']==0)
            {
                now->ch[a[i]-'a']=new_node();
                now->ch[a[i]-'a']->father=now;
            }
            now=now->ch[a[i]-'a'];
        }
    }
    static node * que[100005];
    que[0]=root;
    int front=0,rail=1;
    root->fail=root;
    for (;front<rail;front++)
    {
        que[front]->id=front;
        int i;
        for (i=0;i<26;i++)
        {
            if (que[front]->ch[i]==0)
            {
                if (que[front]==root) que[front]->ch[i]=root;
                que[front]->ch[i]=que[front]->fail->ch[i];
                continue;
            }
            que[rail++]=que[front]->ch[i];
            if (que[front]==root)
            {
                que[front]->ch[i]->fail=root;
            }
            else
            {
                que[front]->ch[i]->fail=que[front]->fail->ch[i];
            }
        }
    }
    for (i=1;i<rail;i++)
    {
        insert_edge(que[i]->fail->id,i);
    }
    int n=rail;
    dfs(0);
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        c[i].read();
        c[i].id=i;
    }
    sort(c,c+m);
    c[m].y=-1;
    now=root;
    int x=0;
    sum=0;
    for (i=0;a[i]!='\0';i++)
    {
        if (a[i]=='P')
        {
            for (;c[x].y==sum;)
            {
                ans[c[x].id]=querys(0,0,n,dfn[b[c[x].x]->id],dfn[b[c[x].x]->id]+size[b[c[x].x]->id]);
                x++;
            }
            sum++;
        }
        else if (a[i]=='B')
        {
            change(0,0,n,dfn[now->id],0);
            now=now->father;
        }
        else
        {
            now=now->ch[a[i]-'a'];
            change(0,0,n,dfn[now->id],1);
        }
    }
    for (i=0;i<m;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}