如标题所言，我已经沉迷于AC自动机无法自拔了。。。

这又是一道AC自动的题，红红火火恍恍惚惚

这题目做起来真舒服

简单概括一下：\(AC\)自动机\(fail\)树上树链剖分\(+\)树状数组

这种类型的题其实还蛮多的，比如这道：

$

$

首先把\(AC\)自动机建出来，然后在所有子节点连一条由\(fail\)指向该点的边，这样一棵\(fail\)树就出来了。

题目问的是：求\(x\)在\(y\)中出现多少次，把问题放到\(fail\)树上来，就变成了：求从根到\(y\)的的节点中（这里指的是\(dfs\)序从根到\(y\)），有多少个在\(x\)的子树内

那么这个东西就很好求了，像普通的树链剖分题那样，用线段树就能维护，但是这道题只要查\(root\)到\(y\)，\(bit\)也适用且常数要更小些

具体做法：我们离线来做这道题，把\(y\)相同的询问放到一起来处理

考虑这样几个做法：

1. 每次遇到\('P'\)则统计答案当前点\(y\)的所有询问的答案；
2. 遇到\('B'\)则将当前点的\(dfn\)从\(bit\)（或线段树）中删除；
3. 否则往下跳，并将该节点插入\(bit\)（或线段树）；

//made by Hero_of_Someone#include
    
     #include
     
      #include
      
       #include
       
        #define N (100010)using namespace std;char s[N];struct Trie{  int size,root;  int son[N][26],fail[N];  int val[N],n,fa[N],ans[N];    void init(){ size=1,root=0; }    void insert(){    int cur=root;    for(int i=0;s[i];i++){      if(s[i]=='P') val[++n]=cur;      else if(s[i]=='B') cur=fa[cur];      else{    int id=s[i]-'a';    if(!son[cur][id]) son[cur][id]=size++;    fa[son[cur][id]]=cur,cur=son[cur][id];      }    }  }  int num,head[N],nxt[N],to[N];  void add(int u,int v){    nxt[++num]=head[u];to[num]=v;head[u]=num;  }    void build(){    int que[N];    int hd=0,tl=0;    for(int i=0;i<26;i++)      if(son[root][i]){    que[tl++]=son[root][i];    fail[son[root][i]]=root;      }      else son[root][i]=root;      while(hd
        
         p[N];    void Ans(){    int m; scanf("%d",&m);    for(int i=1;i<=m;i++){      int x,y; scanf("%d%d",&x,&y);      p[val[y]].push_back((node){x,i});    }    int x=0;    for(int i=0;s[i];i++){      if(s[i]=='P')    for(int j=0,l=p[x].size();j