阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。
打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：
·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
·按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
·按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
输出格式：
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
数据范围:
对于100%的数据，n<=100000,m<=100000,第一行总长度<=100000。
花了大半天才A掉这题（洛谷上A了，BZOJ蜜汁RE，还是太菜）。
对输入的字符串构一个AC自动机，遇到P的时候标记一下节点，遇到B的时候往上退到爸爸那儿。
对于每一个询问(x,y)，如果从根节点到y的路径上有一个节点的fail能连到x，说明x在y中出现了一次。只需要从根节点到y每个点都跑一次，就可以暴力出(x,y)的结果。
但是这样肯定会超时，咋办？
我们考虑根据fail函数，把每条失配边反过来建一个树，再根据这个树搞一个dfs序列。记录一下跑到每个点和跑出每个点的时间戳。
这样有啥用？
根据dfs序列的性质，序列中跑入和跑出这个点的一大坨就是这个点的儿子们。
我们对dfs序列做一个树状数组。那么我们遍历一下Tire，每跑到一个点就给这个点在序列中出现的地方+1(s)，回去之后再-1(s)。跑到一个标记过的结点（到P），以这个点为(y)，根据询问中所有的x，把x出现到跑出的那一段和求出来即可。
代码巨臭。
#include <bits/stdc++.h> using namespace std; #define maxn 100010 #define size 26 int bit[maxn]; char s[maxn]; int head[maxn]; struct Edge{ int next,to; }edges[maxn]; int b_cnt=0; void addedge(int u,int v) { edges[++b_cnt].next=head[u]; edges[b_cnt].to=v; head[u]=b_cnt; return ; } Edge e2[maxn]; int h1[maxn]; int lowbit(int x) { return x&-x; } int cnt; int l[maxn],r[maxn]; void add(int x,int val) { while (x<=cnt) { bit[x]+=val; x+=lowbit(x); } } int query(int x) { int ret=0; while (x>0) { ret+=bit[x]; x-=lowbit(x); } return ret; } int ans[maxn]; struct AcAuto{ int ch[maxn][size]; int father[maxn]; int val[maxn]; int pos[maxn]; int tot; int idx(char c) { return c-'a'; } void build(char *s) { int len=strlen(s); int u=0,id=0; for (int i=0;i<len;i++) { if (s[i]=='P') { pos[++id]=u;//标记打印结点 val[u]=1; } else if (s[i]=='B') u=father[u];//删除，退回到父节点 else{ int c=idx(s[i]); if (!ch[u][c]) { ch[u][c]=++tot; father[tot]=u; } u=ch[u][c]; } } } int fail[maxn]; void getFail() { queue<int> Q; fail[0]=0; for (int c=0;c<26;c++) { if (ch[0][c]) { fail[ch[0][c]]=0; Q.push(ch[0][c]); } } while (!Q.empty()) { int u=Q.front();Q.pop(); for (int i=0;i<26;i++) if (ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],Q.push(ch[u][i]); else ch[u][i]=ch[fail[u]][i]; } } void work(char *s) { int u=0; int id=0; int now=0; for (int i=0;i<strlen(s);i++) { if (s[i]=='P') { id++; for (int y=h1[id];y;y=e2[y].next) { int t=pos[e2[y].to]; ans[y]=query(r[t])-query(l[t]-1); } } else if(s[i]=='B') add(l[u],-1),u=father[u]; else u=ch[u][idx(s[i])],add(l[u],1); } } }ac; int dfs_clock; void dfs(int now) { dfs_clock++; l[now]=dfs_clock; for (int i=head[now];i;i=edges[i].next) { dfs(edges[i].to); } r[now]=dfs_clock; } int main() { scanf("%s",s); ac.build(s); int m; ac.getFail(); dfs_clock=-1; for (int i=1;i<=ac.tot;i++) addedge(ac.fail[i],i); dfs(0); scanf("%d",&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d",&x); scanf("%d",&y); e2[i].next =h1[y]; e2[i].to=x; h1[y]=i; } memset(bit,0,sizeof(bit)); cnt=dfs_clock; ac.work(s); for (int i=1;i<=m;i++) cout<<ans[i]<<endl; }
