【题解】[bzoj2555] Substring

要求实现两种操作:

(1): 在当前字符串的后面插入一个字符串

(2): 询问字符串 $s$ 在当前字符串中出现了几次?(作为连续子串)

你必须在线支持这些操作。

长度 $\leq 600000$,询问次数 $\leq 10000$,询问总长度 $\leq 3,000,000$。

一直听说有 $\rm LCT$ 维护 $parent$ 树的题,没想到真做到了233。

考虑字符串 $s$ 出现的次数,在SAM中,一个节点里面的某个子串的出现次数就是它的子树的出现次数和,因为长的后缀与短的后缀之间信息不共享,所以修改操作本质上是在进行 $parent$ 树上的链加。

考虑一种神奇的写法。每次对于新建的节点 $np$ ,他的贡献应该是 $parent$ 树上 $1\sim np$ 这条路径上的所有点。于是考虑先 merge(1, np) ,把 $np$ 给 splay 上去之后内部就变成了一棵以 $np$ 为根的一条链,这样就可以不用考虑链加,直接在 $np$ 处打标记即可。

似乎查询操作更为神奇。因为查询的时候只需要对于走到的一个点 $x$ ,直接把他 splay 掉就可以维护信息。看上去似乎不是很对,因为对 $x$ 产生贡献的是一颗子树而不是一条链。但这样做其实有他独特的正确性保证,即每个点都存在且仅存在于一棵 splay ,换 splay 的时候势必要 access,而 access 时本质上就已经把原来的标记给下放干净了,所以每次只有可能是当前的 splay 还有信息没有维护清楚。也就是每次只需要管一条链,剩下的链的标记已经清完了。这样就只需要 splay 一下即可。

写的时候,为了卡常发现了个更神奇的地方,就是在SAM里面抠点插子树/插点这两个操作,由于都保证了父亲不存在,所以 Link 这个操作,本质上是不需要 make_root 的,实测这样就会快很多很多。

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
#include <cstdio>
#include <cstring>
#include <iostream>

#define il inline
#define fa(x) t[x].fa
#define rv(x) t[x].rev
#define vl(x) t[x].val
#define tg(x) t[x].tag
#define lc(x) t[x].son[0]
#define rc(x) t[x].son[1]

using namespace std ;

const int N = 1000010 ;
const int M = 1500010 ;

struct LCT{
int fa ;
int rev ;
int val ;
int tag ;
int son[2] ;
}t[M] ;
int n ;
int m ;
int tp ;
int len ;
int ans ;
int res ;
char s[N] ;
char o[N] ;
int stk[M] ;

bool nroot(int x){
return ((lc(fa(x)) == x) || (rc(fa(x)) == x)) ;
}
void reverse(int x){
rv(x) ^= 1 ; swap(lc(x), rc(x)) ;
}
void _down(int x){
if (rv(x)){
rv(x) = 0 ;
if (lc(x)) reverse(lc(x)) ;
if (rc(x)) reverse(rc(x)) ;
}
if (tg(x)){
if (lc(x)) vl(lc(x)) += tg(x), tg(lc(x)) += tg(x) ;
if (rc(x)) vl(rc(x)) += tg(x), tg(rc(x)) += tg(x) ;
tg(x) = 0 ;
}
}
void rotate(int x){
bool w = x == rc(fa(x)) ;
int f1 = fa(x), f2 = fa(f1) ;
if (nroot(f1))
t[f2].son[f1 == rc(f2)] = x ;
t[f1].son[w] = t[x].son[w ^ 1] ;
fa( t[x].son[w ^ 1] ) = f1 ;
fa(x) = f2 ; fa(f1) = x ;
t[x].son[w ^ 1] = f1 ;
}
void splay(int x){
int y = x ;
stk[++ tp] = y ;
while (nroot(y))
stk[++ tp] = (y = fa(y)) ;
while (tp) _down(stk[tp --]) ;
while (nroot(x)){
int f1 = fa(x) ;
int f2 = fa(f1) ;
if (nroot(f1)){
if ((rc(f1) == x) == (rc(f2) == f1))
rotate(f1) ; else rotate(x) ;
}
rotate(x) ;
}
}
il void access(int x){
int y = 0 ;
for ( ; x ; x = fa(y = x))
splay(x), rc(x) = y ;
}
il void make_root(int x){
access(x) ;
splay(x) ; reverse(x) ;
}
il int find_root(int x){
access(x) ; splay(x) ;
while(lc(x)) x = lc(x) ;
return x ;
}
il void merge(int x, int y){
make_root(x) ;
access(y) ; splay(y) ;
}
il void link(int x, int y){
fa(x) = y ;
}
il void cut(int x, int y){
merge(x, y) ;
fa(x) = t[y].son[0] = 0 ;
}
il void Input(int mk) {
len = strlen(s) ;
for (int j = 0 ; j < len ; ++ j)
mk = (mk * 131 + j) % len, swap(s[j], s[mk]) ;
}
struct SAM{
int size ;
int last ;
int len[M] ;
int fal[M] ;
int trans[M][2] ;
void Init(){
last = ++ size ;
}
void Ins(int x){
int np = ++ size ;
int q, nq, p = last ;
len[last = np] = len[p] + 1 ;
while (p && !trans[p][x])
trans[p][x] = np, p = fal[p] ;
if (!p){
fal[np] = 1 ;
link(np, 1), merge(1, np) ;
vl(np) ++, tg(np) ++ ; return ;
}
q = trans[p][x] ;
if (len[q] == len[p] + 1){
fal[np] = q ;
link(np, q), merge(1, np) ;
vl(np) ++, tg(np) ++ ; return ;
}
nq = ++ size ;
cut(fal[q], q) ;
fal[nq] = fal[q] ;
link (q, nq) ;
link (np, nq) ;
link (nq, fal[q]) ;
len[nq] = len[p] + 1 ;
fal[q] = fal[np] = nq ;
splay(q) ; vl(nq) = vl(q) ;
memcpy(trans[nq], trans[q], 8) ;
while (p && trans[p][x] == q)
trans[p][x] = nq, p = fal[p] ;
merge(1, np), vl(np) ++, tg(np) ++ ;
}
}S ;
int main(){
cin >> m ;
scanf("%s", s + 1) ;
len = strlen(s + 1) ; S.Init() ;
for (int i = 1 ; i <= len ; ++ i) S.Ins(s[i] - 'A') ;
while (m --){
scanf("%s", o + 1) ;
scanf("%s", s), Input(ans) ;
if (o[1] == 'A'){
for (int i = 0 ; i < len ; ++ i)
S.Ins(s[i] - 'A') ; //, cout << i << endl ;
}
else{
int rt = 1 ;
for (int i = 0 ; i < len ; ++ i){
rt = S.trans[rt][s[i] - 'A'] ;
if (!rt) break ;
}
if (!rt) res = 0 ;
else splay(rt), res = vl(rt) ;
printf("%d\n", res) ; ans = ans ^ res ;
}
}
return 0 ;
}