String – HDU 5891 – Virtual Judge (vjudge.net)
题意：有一个字符串，每次可以在尾部加一个字符，或者询问某个区间中最长的出现至少两次的子串长度。
字符串初始长度和操作数不超过 $5 \times 10^4$，强制在线。
思路和用后缀自动机 + LCT + 线段树统计区间本质不同子串数是很类似的，对每个右端点开一个可持久化线段树，然后维护关于左端点的信息。
考虑我们在 Access 操作时当前的一段上一次被访问到的时间是 $t$，设在后缀自动机上的最长串长是 $val_x$，那么 $[t – val_x + 1, t]$ 就是一个出现了两次的子串。
首先如果某次询问的 $l \le t – val_x + 1$，那么这个子串对这个询问的贡献就是 $val_x$，在线段树上进行一次单点修改，询问时求一下 $[l, r]$ 最大值即可。
还有一种情况是 $t – val_x + 1 < l \le t$，这时这个子串对询问的贡献应当是 $t + 1 – l$（画一个图可以看得更明显）。考虑到 $-l$ 是固定的，我们可以开另一个线段树维护这部分，把 $t – val_x + 1$ 位置对 $t + 1$ 取 max，询问就变成了查询 $[1, l]$ 最大值再减去 $l$。（对于 $l > t$ 的情况不比特殊处理，因为减去 $l$ 之后会 $\le 0$，自然对答案没有影响。）
因为修改的位置是一样的所以开一个线段树同时存两个值就行了，询问的时候再分开询问。因为要可持久化，时空复杂度都是 $O(n\log^2 n)$。
另外因为本题强制在线，不能先处理出 SAM 形态再挨个 Access。在 fail 树上加一个叶子是很简单的，插入一个结点要注意一下写法，之前写的时候因为对 LCT 的原理记不清了导致写错了，查了很久。
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 200005, maxm = maxn * 17 * 15;
int mx[maxm][2], lc[maxm], rc[maxm], seg_cnt;
int root[maxn];
int s, t, d;
void modify_seg(int l, int r, int &o) {
int u = o;
o = ++seg_cnt;
mx[o][0] = max(mx[u][0], t);
mx[o][1] = max(mx[u][1], d);
if (l == r)
return;
lc[o] = lc[u];
rc[o] = rc[u];
int mid = (l + r) / 2;
if (s <= mid)
modify_seg(l, mid, lc[o]);
else
modify_seg(mid + 1, r, rc[o]);
}
int query_seg(int l, int r, int o, int k) {
if (s <= l && t >= r)
return mx[o][k];
int mid = (l + r) / 2, ans = 0;
if (s <= mid)
ans = max(ans, query_seg(l, mid, lc[o], k));
if (t > mid)
ans = max(ans, query_seg(mid + 1, r, rc[o], k));
return ans;
}
int N;
void modify(int pos, int u, int v, int &rt) {
// printf("modify pos = %d u = %d v = %d\n", pos, u, v);
s = pos;
t = u;
d = v;
modify_seg(1, N, rt);
}
int query(int l, int r, int rt) {
s = l;
t = r;
int ans = query_seg(1, N, rt, 0);
s = 1;
t = l;
return max(ans, query_seg(1, N, rt, 1) - l);
}
struct node {
int size, l, r, id, tim;
node *ch[2], *p;
bool tag;
node() = default;
void apply(int v) {
tim = v;
tag = true;
// update();
}
void pushdown() {
if (tag) {
ch[0] -> tim = ch[1] -> tim = tim;
ch[0] -> tag = ch[1] -> tag = true;
tag = false;
}
}
void update() {
size = ch[0] -> size + ch[1] -> size + 1;
l = (ch[0] -> l ? ch[0] -> l : id);
r = (ch[1] -> r ? ch[1] -> r : id);
}
} null[maxn];
inline bool isroot(node *x) {
return x != x -> p -> ch[0] && x != x -> p -> ch[1];
}
inline bool dir(node *x) {
return x == x -> p -> ch[1];
}
void init(node *x, int i) {
*x = node();
x -> ch[0] = x -> ch[1] = x -> p = null;
x -> size = 1;
x -> id = x -> l = x -> r = i;
}
void rot(node *x, int d) {
node *y = x -> ch[d ^ 1];
y -> p = x -> p;
if (!isroot(x))
x -> p -> ch[dir(x)] = y;
if ((x -> ch[d ^ 1] = y -> ch[d]) != null)
y -> ch[d] -> p = x;
(y -> ch[d] = x) -> p = y;
x -> update();
y -> update();
}
void splay(node *x) {
x -> pushdown();
while (!isroot(x)) {
if (!isroot(x -> p))
x -> p -> p -> pushdown();
x -> p -> pushdown();
x -> pushdown();
if (isroot(x -> p)) {
rot(x -> p, dir(x) ^ 1);
break;
}
if (dir(x) == dir(x -> p))
rot(x -> p -> p, dir(x -> p) ^ 1);
else
rot(x -> p, dir(x) ^ 1);
rot(x -> p, dir(x) ^ 1);
}
}
void splay(node *x, node *rt) {
x -> pushdown();
while (x -> p != rt) {
if (x -> p -> p != rt)
x -> p -> p -> pushdown();
x -> p -> pushdown();
x -> pushdown();
if (x -> p -> p == rt) {
rot(x -> p, dir(x) ^ 1);
break;
}
if (dir(x) == dir(x -> p))
rot(x -> p -> p, dir(x -> p) ^ 1);
else
rot(x -> p, dir(x) ^ 1);
rot(x -> p, dir(x) ^ 1);
}
}
int val[maxn], par[maxn], go[maxn][26], sam_cnt, sam_last;
node *access(node *x, int r) {
root[r] = root[r - 1];
node *y = null;
while (x != null) {
// printf("x = %d\n", (int)(x - null));
splay(x);
x -> pushdown();
x -> ch[1] = null;
x -> update();
if (x -> tim && val[x -> r]) { // last time visited
int right = x -> tim, left = right - val[x -> r] + 1;
// printf("left = %d right = %d\n", left, right);
modify(left, val[x -> r], right + 1, root[r]);
}
x -> apply(r);
x -> pushdown();
x -> ch[1] = y;
(y = x) -> update();
x = x -> p;
}
return y;
}
void new_leaf(node *x, node *par) {
x -> p = par;
}
void new_node(node *x, node *y, node *par) {
splay(y);
if (isroot(y) && y -> p == par) {
assert(y -> ch[0] == null);
y -> ch[0] = x;
x -> p = y;
y -> update();
}
else {
splay(par, y);
assert(y -> ch[0] == par);
assert(par -> ch[1] == null);
par -> ch[1] = x;
x -> p = par;
par -> update();
y -> update();
}
x -> tim = y -> tim;
}
void extend(int c) {
int p = sam_last, np = ++sam_cnt;
val[np] = val[p] + 1;
init(null + np, np);
while (p && !go[p][c]) {
go[p][c] = np;
p = par[p];
}
if (!p) {
par[np] = 1;
new_leaf(null + np, null + par[np]);
}
else {
int q = go[p][c];
if (val[q] == val[p] + 1) {
par[np] = q;
new_leaf(null + np, null + par[np]);
}
else {
int nq = ++sam_cnt;
val[nq] = val[p] + 1;
// printf("nq = %d\n", nq);
memcpy(go[nq], go[q], sizeof(go[q]));
init(null + nq, nq);
// printf("p = %d q = %d par[q] = %d\n", p, q, par[q]);
new_node(null + nq, null + q, null + par[q]);
new_leaf(null + np, null + nq);
par[nq] = par[q];
par[np] = par[q] = nq;
while (p && go[p][c] == q) {
go[p][c] = nq;
p = par[p];
}
}
}
sam_last = np;
}
char str[maxn];
int main() {
init(null, 0);
sam_last = sam_cnt = 1;
init(null + 1, 1);
int n, m;
scanf("%s%d", str + 1, &m);
n = strlen(str + 1);
N = n + m;
for (int i = 1; i <= n; i++) {
// printf("\n--- now i = %d ---\n", i);
extend(str[i] - 'a');
access(null + sam_last, i);
}
// printf("\nsam_cnt = %d\n", sam_cnt);
// for (int i = 1; i <= sam_cnt; i++) {
// printf("i = %d par = %d val = %d go:", i, par[i], val[i]);
// for (int c = 0; c < 26; c++)
// if (go[i][c])
// printf(" {%c %d}", c + 'a', go[i][c]);
// printf("\n");
// }
int tmp = 0;
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
scanf(" %c", &str[++n]);
str[n] = (str[n] - 'a' + tmp) % 26 + 'a';
extend(str[n] - 'a');
access(null + sam_last, n);
}
else {
int l, r;
scanf("%d%d", &l, &r);
l = (l - 1 + tmp) % n + 1;
r = (r - 1 + tmp) % n + 1;
printf("%d\n", tmp = query(l, r, root[r]));
}
}
return 0;
}
