阿狸的打印机问题（AC自动机与线段树在NOI2011的应用）
最编程
2024-07-20 15:26:35
...
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<queue>
5 #include<algorithm>
6 #define N (1000000+100)
7 using namespace std;
8 struct ST
9 {
10 struct node{int val,add;} Segt[N*4];
11 void Push(int node,int l,int r)
12 {
13 if (Segt[node].add!=0)
14 {
15 Segt[node<<1].add=Segt[node<<1].add+Segt[node].add;
16 Segt[node<<1|1].add=Segt[node<<1|1].add+Segt[node].add;
17 int mid=(l+r)>>1;
18 Segt[node<<1].val=Segt[node<<1].val+Segt[node].add*(mid-l+1);
19 Segt[node<<1|1].val=Segt[node<<1|1].val+Segt[node].add*(r-mid);
20 Segt[node].add=0;
21 }
22 }
23 void Update(int node,int l,int r,int l1,int r1,int k)
24 {
25 if (r1<l || l1>r) return;
26 if (l1<=l&&r<=r1)
27 {
28 Segt[node].val=Segt[node].val+k*(r-l+1);
29 Segt[node].add=Segt[node].add+k;
30 return;
31 }
32 Push(node,l,r);
33 int mid=(l+r)>>1;
34 Update(node<<1,l,mid,l1,r1,k);
35 Update(node<<1|1,mid+1,r,l1,r1,k);
36 Segt[node].val=Segt[node<<1].val+Segt[node<<1|1].val;
37 }
38 int Query(int node,int l,int r,int l1,int r1)
39 {
40 if (l1>r||r1<l) return 0;
41 if (l1<=l&&r<=r1) return Segt[node].val;
42 Push(node,l,r);
43 int mid=(l+r)>>1;
44 return Query(node<<1,l,mid,l1,r1)+Query(node<<1|1,mid+1,r,l1,r1);
45 }
46 }Segt_Tree;
47
48 struct node{int x,y,num,ans;}ask[N];
49 struct mode{int to,next;}edge[N];
50 int Son[N][27],Father[N],End[N],end_num,Fail[N];
51 int T_NUM[N],cnt,Size[N];
52 int m,sz,head[N],num_edge;
53 char s[N];
54 queue<int>q;
55
56 void add(int u,int v)
57 {
58 edge[++num_edge].to=v;
59 edge[num_edge].next=head[u];
60 head[u]=num_edge;
61 }
62
63 void Build_AC()
64 {
65 int now=0,len=strlen(s);
66 for (int i=0; i<len; ++i)
67 {
68 int x=s[i]-'a';
69 if (s[i]=='P')
70 {
71 End[++end_num]=now;
72 continue;
73 }
74 if (s[i]=='B')
75 {
76 now=Father[now];
77 continue;
78 }
79 if (!Son[now][x])
80 {
81 Son[now][x]=++sz;
82 Father[sz]=now;
83 }
84 now=Son[now][x];
85 }
86 }
87
88 void Build_Fail()
89 {
90 for (int i=0; i<26; ++i)
91 if (Son[0][i])
92 q.push(Son[0][i]),add(0,Son[0][i]);
93 while (!q.empty())
94 {
95 int now=q.front();
96 q.pop();
97 for (int i=0; i<26; ++i)
98 {
99 if (!Son[now][i])
100 {
101 Son[now][i]=Son[Fail[now]][i];
102 continue;
103 }
104 Fail[Son[now][i]]=Son[Fail[now]][i];
105 add(Fail[Son[now][i]],Son[now][i]);
106 q.push(Son[now][i]);
107 }
108 }
109 }
110
111 void Dfs(int x)
112 {
113 T_NUM[x]=++cnt;
114 Size[x]=1;
115 for (int i=head[x]; i; i=edge[i].next)
116 Dfs(edge[i].to),Size[x]+=Size[edge[i].to];
117 }
118
119 bool cmp(node a,node b){return a.y<b.y;}
120 bool cmq(node a,node b){return a.num<b.num;}
121 int main()
122 {
123 scanf("%s",s);
124 Build_AC();
125 Build_Fail();
126 Dfs(0);
127 scanf("%d",&m);
128 for (int i=1; i<=m; ++i)
129 scanf("%d%d",&ask[i].x,&ask[i].y),ask[i].num=i;
130 sort(ask+1,ask+m+1,cmp);
131 int now=0,p=1,word_num=0,len=strlen(s);
132 for (int i=0; i<len; ++i)
133 {
134 switch (s[i])
135 {
136 case 'P':
137 {
138 word_num++;
139
140 while (ask[p].y<word_num && p<=m) p++;
141 while (ask[p].y==word_num && p<=m)
142 {
143 int x=ask[p].x;
144 ask[p].ans=Segt_Tree.Query(1,1,len,T_NUM[End[x]],T_NUM[End[x]]+Size[End[x]]-1);
145 p++;
146 }
147 break;
148 }
149 case 'B':
150 {
151 Segt_Tree.Update(1,1,len,T_NUM[now],T_NUM[now],-1);
152 now=Father[now];
153 break;
154 }
155 default:
156 {
157 int x=s[i]-'a';
158 now=Son[now][x];
159 Segt_Tree.Update(1,1,len,T_NUM[now],T_NUM[now],1);
160 }
161 }
162 }
163 sort(ask+1,ask+m+1,cmq);
164 for (int i=1;i<=m;++i)
165 printf("%d\n",ask[i].ans);
166 }