- 在当前字符串的后面插入一个字符串；
- 询问字符串 在当前字符串中出现了几次？（作为连续子串）
链接
题解
在线查询字符串的出现次数，需要在线维护 集合的大小。使用 Link-Cut Tree 维护有根树的子树和。每次 Link 两个节点后，重新将根节点置为有根树的根，然后将子节点的权值加到父节点到根的一条链上；反之，Cut 后要将其减去。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 600000;
const int MAXL = 3000000;
const int MAXM = 10000;
const int CHARSET_SIZE = 26;
struct LinkCutTree {
struct Node {
Node *ch[2], *fa, *pathFa;
int val, tag;
bool rev;
int relation() {
return this == fa->ch[1];
}
void pushDown() {
if (rev) {
rev ^= 1;
std::swap(ch[0], ch[1]);
if (ch[0]) ch[0]->rev ^= 1;
if (ch[1]) ch[1]->rev ^= 1;
}
if (tag) {
if (ch[0]) ch[0]->add(tag);
if (ch[1]) ch[1]->add(tag);
tag = 0;
}
}
void rotate() {
pushDown();
int r = relation();
Node *o = fa;
std::swap(pathFa, o->pathFa);
fa = o->fa;
if (o->fa) o->fa->ch[o->relation()] = this;
o->ch[r] = ch[r ^ 1];
if (ch[r ^ 1]) ch[r ^ 1]->fa = o;
ch[r ^ 1] = o;
o->fa = this;
}
void splay() {
while (fa) {
if (fa->fa) fa->fa->pushDown();
fa->pushDown();
if (!fa->fa) rotate();
else if (fa->relation() == relation()) fa->rotate(), rotate();
else rotate(), rotate();
}
}
void expose() {
splay();
pushDown();
if (ch[1]) {
std::swap(ch[1]->fa, ch[1]->pathFa);
ch[1] = NULL;
}
}
bool splice() {
splay();
if (!pathFa) return false;
pathFa->expose();
pathFa->ch[1] = this;
std::swap(pathFa, fa);
return true;
}
void access() {
expose();
while (splice());
}
void evert() {
access();
splay();
rev ^= 1;
}
void add(int delta) {
val += delta;
tag += delta;
}
} N[MAXN * 2 + 1];
void link(int fa, int ch) {
Node *f = &N[fa], *c = &N[ch];
f->evert();
c->splay();
c->pathFa = f;
N[0].evert();
f->access();
f->splay();
f->val += c->val;
if (f->ch[0]) f->ch[0]->add(c->val);
}
void cut(int fa, int ch) {
Node *f = &N[fa], *c = &N[ch];
f->evert();
c->access();
f->splay();
f->pushDown();
f->ch[1] = NULL;
c->fa = NULL;
N[0].evert();
f->access();
f->splay();
f->val -= c->val;
if (f->ch[0]) f->ch[0]->add(-c->val);
}
void update(int u, int val) {
N[u].val = val;
}
int query(int u) {
Node *a = &N[u];
a->splay();
return a->val;
}
} lct;
struct SuffixAutomaton {
struct Node {
Node *ch[CHARSET_SIZE], *next;
int max;
Node(int max = 0) : ch(), next(NULL), max(max) {}
} *start, *last, _pool[MAXN * 2 + 1], *_curr;
void init() {
_curr = _pool;
start = last = new (_curr++) Node;
}
int id(Node *v) {
return v - _pool;
}
Node *extend(int c) {
Node *u = new (_curr++) Node(last->max + 1), *v = last;
lct.update(id(u), 1);
do {
v->ch[c] = u;
v = v->next;
} while (v && !v->ch[c]);
if (!v) {
u->next = start;
lct.link(id(start), id(u));
} else if (v->ch[c]->max == v->max + 1) {
u->next = v->ch[c];
lct.link(id(v->ch[c]), id(u));
} else {
Node *n = new (_curr++) Node(v->max + 1), *o = v->ch[c];
std::copy(o->ch, o->ch + CHARSET_SIZE, n->ch);
lct.cut(id(o->next), id(o));
lct.link(id(o->next), id(n));
lct.link(id(n), id(o));
lct.link(id(n), id(u));
n->next = o->next;
o->next = u->next = n;
for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
}
last = u;
return u;
}
} sam;
char s[MAXL + 2];
int len;
inline void decode(int mask) {
for (int i = 0; i < len; i++) {
mask = (mask * 131 + i) % len;
std::swap(s[i + 1], s[mask + 1]);
}
}
inline void extend() {
for (int i = 1; i <= len; i++) sam.extend(s[i] - 'A');
}
inline int solve() {
SuffixAutomaton::Node *v = sam.start;
for (int i = 1; i <= len; i++) {
int c = s[i] - 'A';
if (!v->ch[c]) return 0;
v = v->ch[c];
}
return lct.query(sam.id(v));
}
int main() {
int q;
scanf("%d", &q);
sam.init();
scanf("%s", s + 1);
len = strlen(s + 1);
extend();
int mask = 0;
while (q--) {
char type[sizeof("QUERY")];
scanf("%s %s", type, s + 1);
len = strlen(s + 1);
decode(mask);
// puts(s + 1);
if (type[0] == 'Q') {
int ans = solve();
printf("%d\n", ans);
mask ^= ans;
} else {
extend();
}
}
return 0;
}