首页 > 代码库 > 2434: [Noi2011]阿狸的打字机 - BZOJ
2434: [Noi2011]阿狸的打字机 - BZOJ
Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和‘B‘、‘P‘两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有‘B‘的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有‘P‘的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
aPaPBbP
3
1 2
1 3
2 3
Sample Output
2
1
0
HINT
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5
首先我们建出ac自动机，然后对于一组询问（x，y）就是从根到y字符串这条路径有多少点可以通过fail走到x节点，然后fail反向建出来的是一棵树（就叫fail树算了）
于是一组询问（x，y）就是从根到y字符串这条路径有多少点在x节点的子树中，于是我们处理出dfs序，我们就只要维护区间和就行了
对于多组询问我们就离线处理，按照他打字机的顺序遍历点，小写字母就在他的dfs序上+1，B就在现在这个节点的dfs序上-1，走到x单词的结束节点时处理询问（i，x）
1 const 2 maxn=100100; 3 type 4 node=record 5 x,y,id:longint; 6 end; 7 var 8 go:array[0..maxn,‘a‘..‘z‘]of longint; 9 q:array[0..maxn]of node; 10 ch:array[0..maxn]of char; 11 e,p,fa,ll,rr,ans,fail,first,last,next,bit:array[0..maxn]of longint; 12 n,cnt,tot,now,sum:longint; 13 s:ansistring; 14 15 procedure insert(x,y:longint); 16 begin 17 inc(tot); 18 last[tot]:=y; 19 next[tot]:=first[x]; 20 first[x]:=tot; 21 end; 22 23 function nexts(x:longint;c:char):longint; 24 begin 25 if go[x,c]=0 then 26 begin 27 inc(cnt);go[x,c]:=cnt; 28 fa[cnt]:=x;ch[cnt]:=c; 29 end; 30 exit(go[x,c]); 31 end; 32 33 procedure swap(var x,y:node); 34 var 35 t:node; 36 begin 37 t:=x;x:=y;y:=t; 38 end; 39 40 procedure sort(l,r:longint); 41 var 42 i,j,y:longint; 43 begin 44 i:=l;j:=r;y:=q[(l+r)>>1].x; 45 repeat 46 while q[i].x<y do inc(i); 47 while q[j].x>y do dec(j); 48 if i<=j then 49 begin 50 swap(q[i],q[j]); 51 inc(i);dec(j); 52 end; 53 until i>j; 54 if i<r then sort(i,r); 55 if j>l then sort(l,j); 56 end; 57 58 procedure dfs(x:longint); 59 var 60 i:longint; 61 begin 62 inc(sum);ll[x]:=sum; 63 i:=first[x]; 64 while i<>0 do 65 begin 66 dfs(last[i]); 67 i:=next[i]; 68 end; 69 rr[x]:=sum; 70 end; 71 72 var 73 que:array[0..maxn]of longint; 74 l,r:longint; 75 76 procedure bfs; 77 var 78 i,j:longint; 79 c:char; 80 begin 81 que[1]:=0;l:=0;r:=0; 82 while l<=r do 83 begin 84 for c:=‘a‘ to ‘z‘ do 85 if go[que[l],c]>0 then 86 begin 87 inc(r); 88 que[r]:=go[que[l],c]; 89 end; 90 inc(l); 91 end; 92 for i:=1 to cnt do 93 begin 94 j:=que[i];c:=ch[j];j:=fail[fa[j]]; 95 while (j<>0) and (go[j,c]=0) do 96 j:=fail[j]; 97 fail[que[i]]:=go[j,c]; 98 if fail[que[i]]=que[i] then fail[que[i]]:=0; 99 insert(fail[que[i]],que[i]);100 end;101 end;102 103 function get(x:longint):longint;104 begin105 get:=0;106 while x>0 do107 begin108 inc(get,bit[x]);109 x:=x-(x and (-x));110 end;111 end;112 113 procedure add(x,y:longint);114 begin115 while x<=sum do116 begin117 inc(bit[x],y);118 x:=x+(x and (-x));119 end;120 end;121 122 procedure main;123 var124 i,j:longint;125 begin126 readln(s);now:=0;127 for i:=1 to length(s) do128 begin129 if s[i]=‘P‘ then130 begin131 inc(n);132 e[n]:=i;133 p[n]:=now;134 end135 else136 if s[i]=‘B‘ then now:=fa[now]137 else now:=nexts(now,s[i]);138 end;139 bfs;140 dfs(0);141 read(n);142 for i:=1 to n do143 read(q[i].y,q[i].x);144 for i:=1 to n do q[i].id:=i;145 sort(1,n);146 j:=0;now:=0;147 for i:=1 to n do148 begin149 while j<e[q[i].x] do150 begin151 inc(j);152 if s[j]=‘B‘ then153 begin154 add(ll[now],-1);155 now:=fa[now];156 end157 else158 if s[j]<>‘P‘ then159 begin160 now:=nexts(now,s[j]);161 add(ll[now],1);162 end;163 end;164 ans[q[i].id]:=get(rr[p[q[i].y]])-get(ll[p[q[i].y]]-1);165 end;166 for i:=1 to n do writeln(ans[i]);167 end;168 169 begin170 main;171 end.