「BZOJ2555」SubString

Description

懒得写背景了,给你一个字符串initinit,要求你支持两个操作

  1. 在当前字符串的后面插入一个字符串
  2. 询问字符串s在当前字符串中出现了几次?(作为连续子串)
    你必须在线支持这些操作。

Input

第一行一个数QQ表示操作个数
第二行一个字符串表示初始字符串initinit
接下来QQ行,每行22个字符串TypeType,StrStr
TypeTypeADD的话表示在后面插入字符串。
TypeTypeQUERY的话表示询问某字符串在当前字符串中出现了几次。
为了体现在线操作,你需要维护一个变量maskmask,初始值为00

读入串StrStr之后,使用这个过程将之解码成真正询问的串TrueStrTrueStr
询问的时候,对TrueStrTrueStr询问后输出一行答案ResultResult
然后mask=mask xor Resultmask=mask\ xor\ Result
插入的时候,将TrueStrTrueStr插到当前字符串后面即可。

Output

输出每一次询问。

Sample Input

1
2
3
4
2
A
QUERY B
ADD BBABBBBAAB

Sample Output

1
0

HINT

ADDQUERY操作的字符串都需要解压
长度 600000\leq 600000,询问次数10000\leq 10000,询问总长度3000000\leq 3000000

Solution

核心思想就是动态维护EndposEndpos集合的大小。
那么怎么用lctlct来维护子树里的ww值之和呢?
每一次cutcut或者linklink操作,假定parentparent树上xx的深度小于yy的深度,把xx到根的节点减去或者加上wyw_y
查询的时候,直接splaysplay,然后wxw_x就是答案了。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 710000 * 2;
int w[N], tag[N];
char s[N];
int n;
struct Link_cut_Tree {
int fa[N], ch[N][2];
bool nr(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
bool ident(int x) {
return ch[fa[x]][1] == x;
}
void con(int x, int F, int how) {
ch[F][how] = x;
fa[x] = F;
}
int st[N], top;
void rotate(int x) {
int y = fa[x], z;
if(ident(x)) {
z = ch[x][0];
fa[x] = fa[y];
if(nr(y)) con(x, fa[y], ident(y));
con(y, x, 0);
con(z, y, 1);
} else {
z = ch[x][1];
fa[x] = fa[y];
if(nr(y)) con(x, fa[y], ident(y));
con(y, x, 1);
con(z, y, 0);
}
}
void down(int x) {
if(tag[x]) {
w[ch[x][0]] += tag[x];
w[ch[x][1]] += tag[x];
tag[ch[x][0]] += tag[x];
tag[ch[x][1]] += tag[x];
tag[x] = 0;
}
}
void splay(int x) {
top = 0;
int y = x;
while(nr(y)) st[++top] = y, y = fa[y];
st[++top] = y;
while(top) down(st[top--]);
for(int y = fa[x]; nr(x); y = fa[x]) {
if(nr(y)) rotate(ident(x) == ident(y) ? y : x);
rotate(x);
}
}
void access(int x) {
for(int y = 0; x; x = fa[y = x])
splay(x), ch[x][1] = y;
}
void cut(int x, int y) { //x->y
access(x);
splay(x);
access(y);
splay(y);
tag[x] -= w[y];
w[x] -= w[y];
ch[y][0] = fa[x] = 0;

/* access(y);
splay(y);
w[ch[y][0]] -= w[y];
tag[ch[y][0]] -= w[y];
ch[y][0] = fa[ch[y][0]] = 0;*/
}
void link(int x, int y) { //x->y
access(y);
splay(y);
fa[y] = x;
access(x);
splay(x);
tag[x] += w[y];
w[x] += w[y];
}
}lct;
struct SuffixAutoMaton {
int ch[N][26], last, num;
int len[N], fa[N];
void ins(int c) {
int np = ++num, p = last; len[np] = len[p] + 1; last = np;
w[np] = 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) fa[np] = 1;
else {
int q = ch[p][c];
if(len[q] == len[p] + 1) fa[np] = q, lct.link(q, np);
else {
// puts("OK");
int nq = ++num; len[nq] = len[p] + 1; memmove(ch[nq],ch[q],sizeof ch[q]);
lct.cut(fa[q], q);
lct.link(fa[q], nq);
lct.link(nq, q);
lct.link(nq, np);
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
}
}
}sam;
int Q;
char op[8];
void get(int mask) {
for(int i = 0; i < n; ++i) {
mask = (mask * 131 + i) % n;
swap(s[i], s[mask]);
}
}
int query() {
int p = 1;
for(int i = 0; i < n; ++i) {
if(!sam.ch[p][s[i] - 'A']) {
return 0;
}
p = sam.ch[p][s[i] - 'A'];
}
lct.splay(p);
return w[p];
}
int main() {
sam.last = sam.num = 1;
Q = read();
cin>>(s+1);
n = strlen(s +1);
for(int i = 1; i <= n; ++i)
sam.ins(s[i] - 'A');
int mask = 0;
for(int T = 1; T <= Q; ++T) {
scanf("%s%s", op,s);
n = strlen(s);
get(mask);
if(op[0] == 'A') {
for(int j = 0; j < n; ++j)
sam.ins(s[j] - 'A');
} else {
int t = query();
writeln(t);
mask ^= t;
}
}
return 0;
}