阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和‘B‘、‘P‘两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有‘B‘的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有‘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个询问的答案。
1<=N<=10^5
其实不是很难。
首先我们画画图很容易想到的就是在fail树上求子树和，然后单点暴力修改每个串，这样就是70分。
然后之所以只有70分，是因为有的点被许多串包含所以被修改多次。
如果我们能让每个点只被修改一次，复杂度就正确了。
其实也不难，我们按建trie的顺序dfs，这样每个点就只会被修改一次了
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 #define M 100010 7 #define ls node*2 8 #define rs node*2+1 9 using namespace std; 10 struct point{ 11 int to,next; 12 }e[M<<1]; 13 struct Ask{ 14 int x,y,id,ans; 15 }ask[M]; 16 17 int n,num,dfn,cnt,Num,tot; 18 int head[M],in[M],out[M]; 19 int end[M],fail[M],fa[M],ch[M][26]; 20 int val[M<<2]; 21 char s[M]; 22 23 void add(int from,int to) 24 { 25 e[++num].next=head[from]; 26 e[num].to=to; 27 head[from]=num; 28 } 29 void dfs(int x) 30 { 31 in[x]=++dfn; 32 for(int i=head[x];i;i=e[i].next) 33 { 34 int to=e[i].to; 35 dfs(to); 36 } 37 out[x]=dfn; 38 } 39 40 void build(string s) 41 { 42 int now=0,len=s.length(); 43 for(int i=0;i<len;i++) 44 { 45 int u=s[i]-‘a‘; 46 if(s[i]==‘P‘) end[++Num]=now; 47 else if(s[i]==‘B‘) now=fa[now]; 48 else 49 { 50 if(!ch[now][u]) 51 { 52 ch[now][u]=++cnt; 53 fa[cnt]=now; 54 } 55 now=ch[now][u]; 56 } 57 } 58 } 59 void build_fail() 60 { 61 queue<int>q; 62 for(int i=0;i<26;i++) 63 if(ch[0][i]) 64 q.push(ch[0][i]); 65 while(!q.empty()) 66 { 67 int u=q.front(); q.pop(); 68 for(int i=0;i<26;i++) 69 { 70 if(ch[u][i]) 71 { 72 fail[ch[u][i]]=ch[fail[u]][i]; 73 q.push(ch[u][i]); 74 } 75 else ch[u][i]=ch[fail[u]][i]; 76 } 77 } 78 } 79 80 int cmp1(Ask x1,Ask x2) {return x1.y<x2.y;} 81 int cmp2(Ask x1,Ask x2) {return x1.id<x2.id;} 82 83 void update(int node) {val[node]=val[ls]+val[rs];} 84 void insert(int node,int l,int r,int k,int v) 85 { 86 if(l==r) 87 { 88 val[node]+=v; 89 return; 90 } 91 int mid=(l+r)/2; 92 if(k<=mid) insert(ls,l,mid,k,v); 93 else insert(rs,mid+1,r,k,v); 94 update(node); 95 } 96 int query(int node,int l,int r,int l1,int r1) 97 { 98 if(l1<=l&&r1>=r) return val[node]; 99 if(l1>r||r1<l) return 0; 100 int mid=(l+r)/2; 101 return query(ls,l,mid,l1,r1)+query(rs,mid+1,r,l1,r1); 102 } 103 104 int main() 105 { 106 scanf("%s",s); 107 build(s); 108 build_fail(); 109 for(int i=1;i<=cnt;i++) add(fail[i],i); 110 dfs(0); 111 scanf("%d",&n); 112 for(int i=1;i<=n;i++) 113 { 114 scanf("%d%d",&ask[i].x,&ask[i].y); 115 ask[i].id=i; 116 } 117 sort(ask+1,ask+1+n,cmp1); 118 int len=strlen(s),p=1,now=0; 119 for(int i=0;i<len;i++) 120 { 121 if(s[i]==‘P‘) 122 { 123 tot++; 124 while(ask[p].y==tot&&p<=n) 125 { 126 int x=ask[p].x; 127 ask[p].ans=query(1,1,len,in[end[x]],out[end[x]]); 128 p++; 129 } 130 } 131 else if(s[i]==‘B‘) 132 { 133 insert(1,1,len,in[now],-1); 134 now=fa[now]; 135 } 136 else 137 { 138 now=ch[now][s[i]-‘a‘]; 139 insert(1,1,len,in[now],1); 140 } 141 } 142 sort(ask+1,ask+1+n,cmp2); 143 for(int i=1;i<=n;i++) printf("%d\n",ask[i].ans); 144 return 0; 145 }
原文：https://www.cnblogs.com/Slrslr/p/9498135.html