Description

维护一个字符串，支持插入字符，修改字符，以及求两个后缀的\(lcp\)。

Solution

建立一棵\(Splay\)来维护整个串，每个节点维护整个子树的哈希值。对于插入，直接在对应的位置插入；修改也直接修改就好；然后一路\(update\)。对于查询，考虑二分，然后每次查询对应区间的哈希值，\(O(1)\)判断即可。

查询某个区间的哈希值，用\(Splay\)写的话比较方便，对于区间\([l,r]\)，直接把\(l-1\)旋转到根，把\(r+1\)旋转到根节点的右儿子，那么根节点的右儿子的左儿子的哈希值就是区间\([l,r]\)的哈希值。

Code

#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int _ = 1e5 + 10;const int __ = 3e5 + 10;const int base = 233;char s[_];int N, M;ull p[__];struct Splay { int fa[__], son[__][2], val[_], siz[_]; ull h[_]; int tot, root; int alloc(int v, int f) { fa[++tot] = f, siz[tot] = 1; son[tot][0] = son[tot][1] = 0; val[tot] = h[tot] = v; return tot; } void update(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1; h[x] = h[son[x][1]] + val[x] * p[siz[son[x][1]]] + h[son[x][0]] * p[siz[son[x][1]] + 1]; } int ident(int x) { return son[fa[x]][1] == x; } void connect(int x, int f, int k) { fa[x] = f, son[f][k] = x; } void rotate(int x) { int y = fa[x], z = fa[y]; if (y == root) root = x; int yson = ident(x), zson = ident(y); int k = son[x][yson ^ 1]; connect(k, y, yson); connect(y, x, yson ^ 1); connect(x, z, zson); update(y), update(x); } void splay(int x, int to) { while (fa[x] != to) { int y = fa[x], z = fa[y]; if (z != to) (ident(x)) ^ (ident(y)) ? rotate(x) : rotate(y); rotate(x); } if (!to) root = x; } int find(int x) { int u = root; while (1) { if (x == siz[son[u][0]] + 1) return u; if (x <= siz[son[u][0]]) u = son[u][0]; else x -= siz[son[u][0]] + 1, u = son[u][1]; } } void insert(int x, int v) { if (!root) { root = alloc(v, 0); return; } int u = find(x); splay(u, 0); if (!son[u][1]) { son[u][1] = alloc(v, u); update(u); return; } else { u = find(x + 1); splay(u, root); son[u][0] = alloc(v, u); update(u), update(root); return; } } void modify(int x, int v) { int u = find(x); splay(u, 0); val[u] = v; update(u); } ull query(int l, int r) { int u = find(l); splay(u, 0); if (l == r) return val[u]; u = find(r); splay(u, root); return h[son[u][0]] * p[1] + val[u] + val[root] * p[siz[son[u][0]] + 1]; }} tr;inline void init(const int lim = 3e5) { p[0] = 1; for (int i = 1; i <= lim; ++i) p[i] = p[i - 1] * base; for (int i = 1; i <= N; ++i) tr.insert(i - 1, s[i] - 'a' + 1);}inline bool check(int x, int y, int len) { return tr.query(x, x + len - 1) == tr.query(y, y + len - 1);}int calc(int x, int y) { int l = 0, r = min(N - x, N - y) + 1; while (l < r) { int mid = (l + r + 1) >> 1; if (check(x, y, mid)) l = mid; else r = mid - 1; } return l;}int main() {#ifndef ONLINE_JUDGE freopen("martian.in", "r", stdin); freopen("martian.out", "w", stdout);#endif scanf("%s%d", s + 1, &M); N = strlen(s + 1); init(); char op[3], v[3]; int x, y; while (M--) { scanf("%s%d", op, &x); if (op[0] == 'Q') { scanf("%d", &y); printf("%d\n", calc(x, y)); } else if (op[0] == 'R') { scanf("%s", v); char c = v[0]; tr.modify(x, c - 'a' + 1); } else if (op[0] == 'I') { scanf("%s", v); char c = v[0]; tr.insert(x, c - 'a' + 1); ++N; } } return 0;}