Substring
题意
题面
给定一个初始字符串, 要求支持在这个字符串后添加字符串/查询某个字符串作为子串的出现次数.
强制在线.
长度 $\le600000$，询问次数 $\le10000$,询问总长度 $\le3000000$.
题解
看上去好像可以KMP增量构造的样子
实际上不行 (每次询问都得遍历一遍原串)
考虑用另一个可以支持快速扩展的维护字符串的算法: SAM.
但是SAM增量构造的时候某个状态对应的 right 集合大小(也就是对应子串的出现次数)是 prt 树上的子树和的形式. 而且这个树的形态会产生改变(又是烦人的nq结点搞的事情).
注意到这里求子树和的时候不会换根, 于是我们可以在每次 link 的时候都把当前点对所有祖先的贡献都通过一次链上操作累加上去. 于是就可以比较容易地用LCT维护了.
然而写假了好几次
一开始写假是因为 Decode 出了锅调了很久…因为我一直以为 mask 在 Decode 的时候也会变…
后来写假是因为 link/cut 的时候没有把整个子树的贡献都累加上去 (这数据比较生草…这么大的错误只挂了一个点…)
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
#include <bits/stdc++.h>
const int MAXN=2e6+10;
int size[MAXN];
#define lch chd[0]
#define rch chd[1]
#define kch chd[k]
#define xch chd[k^1]
struct LinkCutTree{
struct Node{
int val;
int add;
bool rev;
Node* prt;
Node* pprt;
Node* chd[2];
Node(int x):val(x),add(0),rev(false),prt(NULL),pprt(NULL){
this->lch=this->rch=NULL;
}
void Flip(){
if(this!=NULL){
this->rev=!this->rev;
std::swap(this->lch,this->rch);
}
}
void Add(int x){
if(this!=NULL){
this->val+=x;
this->add+=x;
}
}
void PushDown(){
if(this->add!=0){
this->lch->Add(this->add);
this->rch->Add(this->add);
this->add=0;
}
if(this->rev){
this->lch->Flip();
this->rch->Flip();
this->rev=false;
}
}
};
std::vector<Node*> N;
LinkCutTree():N(1){}
void Rotate(Node* root,int k){
Node* tmp=root->xch;
root->PushDown();
tmp->PushDown();
tmp->prt=root->prt;
if(root->prt==NULL){
tmp->pprt=root->pprt;
root->pprt=NULL;
}
else if(root->prt->lch==root)
root->prt->lch=tmp;
else
root->prt->rch=tmp;
root->xch=tmp->kch;
if(root->xch!=NULL)
root->xch->prt=root;
tmp->kch=root;
root->prt=tmp;
}
void Splay(Node* root){
while(root->prt!=NULL){
int k=root->prt->lch==root;
if(root->prt->prt==NULL)
Rotate(root->prt,k);
else{
int d=root->prt->prt->lch==root->prt;
Rotate(k==d?root->prt->prt:root->prt,k);
Rotate(root->prt,d);
}
}
}
void Expose(Node* root){
Splay(root);
root->PushDown();
if(root->rch!=NULL){
root->rch->prt=NULL;
root->rch->pprt=root;
root->rch=NULL;
}
}
bool Splice(Node* root){
Splay(root);
if(root->pprt==NULL)
return false;
Expose(root->pprt);
root->pprt->rch=root;
root->prt=root->pprt;
root->pprt=NULL;
return true;
}
void Access(Node* root){
Expose(root);
while(Splice(root));
assert(root->pprt==0&&root->prt==0);
}
void Evert(Node* root){
Access(root);
root->Flip();
}
void Add(int y,int d){
Evert(N[1]);
Access(N[y]);
N[y]->Add(d);
}
void Link(int prt,int son){
Evert(N[son]);
N[son]->pprt=N[prt];
Evert(N[1]);
Access(N[prt]);
N[prt]->Add(N[son]->val);
}
void Cut(int prt,int son){
Evert(N[1]);
Access(N[son]);
Access(N[prt]);
N[prt]->Add(-N[son]->val);
Access(N[son]);
N[son]->PushDown();
N[son]->lch->prt=NULL;
N[son]->lch=NULL;
}
int Query(int x){
Access(N[x]);
return N[x]->val;
}
void MakeTree(int x){
N.push_back(new Node(x));
}
}*T=new LinkCutTree();
int q;
int cnt=1;
int root=1;
int last=1;
char s[MAXN];
int prt[MAXN];
int len[MAXN];
std::map<char,int> chd[MAXN];
int Query(char*);
void Extend(char);
void Extend(char*);
void Decode(char*,int);
int main(){
scanf("%d",&q);
scanf("%s",s);
T->MakeTree(0);
Extend(s);
int mask=0;
while(q--){
scanf("%s",s);
if(*s=='A'){
scanf("%s",s);
Decode(s,mask);
Extend(s);
}
else{
scanf("%s",s);
Decode(s,mask);
int x=Query(s);
mask^=x;
printf("%d\n",x);
}
}
return 0;
}
int Query(char* s){
int cur=root;
while(*s!='\0'){
if(!chd[cur].count(*s))
return 0;
else
cur=chd[cur][*s];
++s;
}
return T->Query(cur);
}
void Decode(char* s,int mask){
int len=strlen(s);
for(int i=0;i<len;i++){
mask=(mask*131+i)%len;
char t=s[i];
s[i]=s[mask];
s[mask]=t;
}
}
void Extend(char* s){
while(*s!='\0')
Extend(*(s++));
}
void Extend(char x){
int p=last;
int np=++cnt;
T->MakeTree(1);
size[last=np]=1;
len[np]=len[p]+1;
while(p&&!chd[p].count(x))
chd[p][x]=np,p=prt[p];
if(p==0)
prt[np]=root;
else{
int q=chd[p][x];
if(len[q]==len[p]+1)
prt[np]=q;
else{
int nq=++cnt;
T->MakeTree(0);
chd[nq]=chd[q];
prt[nq]=prt[q];
T->Cut(prt[q],q);
T->Link(prt[nq],nq);
prt[q]=nq;
T->Link(nq,q);
prt[np]=nq;
len[nq]=len[p]+1;
while(p&&chd[p][x]==q)
chd[p][x]=nq,p=prt[p];
}
}
T->Link(prt[np],np);
}
|
