我不知道为什么我把 MAXN
从 1e5 + 5
开大到 1e6 + 5
就过了……贴个代码吧
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5;
const int MAXN = N + 5;
const ull BASE = 13331;
ull pw[MAXN];
void hash_init() {
pw[0] = 1;
rep(i, 1, N)
pw[i] = pw[i-1] * BASE;
}
template<typename Val>
struct Splay {
int fa[MAXN], siz[MAXN], tr[MAXN][2];
Val val[MAXN];
ull hsh[MAXN];
int root, tot;
int newNode() {
return ++tot;
}
Splay() {
root = 0;
tot = 0;
int l = newNode();
int r = newNode();
val[l] = '#', val[r] = '#';
root = l;
tr[l][1] = r;
fa[r] = l;
pushup(r);
pushup(l);
}
void pushup(int u) {
siz[u] = siz[tr[u][0]] + siz[tr[u][1]] + 1;
int s = siz[tr[u][1]];
hsh[u] = hsh[tr[u][0]] * pw[s + 1] + (val[u] - 'a' + 1) * pw[s] + hsh[tr[u][1]];
}
bool dir(int u) {
return u == tr[fa[u]][1];
}
void rotate(int u) {
int v = fa[u], w = fa[v];
bool r = dir(u);
tr[v][r] = tr[u][!r];
tr[u][!r] = v;
if (w) tr[w][dir(v)] = u;
if (tr[v][r]) fa[tr[v][r]] = v;
fa[v] = u;
fa[u] = w;
pushup(v), pushup(u);
}
void splay(int u, int target = 0) {
while (fa[u] != target) {
int v = fa[u];
if (fa[v] != target)
rotate(dir(u) == dir(v) ? v : u);
rotate(u);
}
if (!target) root = u;
}
int kth(int x) {
// 找到第 k 个元素所在的节点,并且不 splay
int u = root;
while (true) {
if (x <= siz[tr[u][0]])
u = tr[u][0];
else {
x -= siz[tr[u][0]] + 1;
if (x <= 0)
return u;
u = tr[u][1];
}
}
return -1;
}
void insert(int x, Val k) {
int u = kth(x), v = kth(x+1);
splay(u);
splay(v, u);
int w = newNode();
tr[v][0] = w;
fa[w] = v;
val[w] = k;
splay(w);
}
void assign(int x, Val k) {
int u = kth(x);
splay(u);
val[u] = k;
pushup(u);
}
ull query_hash(int l, int r) {
int u = kth(l-1), v = kth(r+1);
splay(u);
splay(v, u);
return hsh[tr[v][0]];
}
void print(int u) {
if (!u)
return;
print(tr[u][0]);
cerr << val[u];
print(tr[u][1]);
}
void print() {
print(root);
cerr << '\n';
}
};
int n;
Splay<char> tr;
int LCP(int x, int y) {
if (x > y) swap(x, y);
int l = 0, r = n - y + 2, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (tr.query_hash(x, x + mid - 1) == tr.query_hash(y, y + mid - 1)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
return ans;
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
hash_init();
string s; cin >> s; n = s.length();
rep(i, 1, n)
tr.insert(i, s[i-1]);
int q; cin >> q; while (q--) {
char op; cin >> op;
if (op == 'Q') {
int x, y; cin >> x >> y;
cout << LCP(x+1, y+1) << '\n';
} else if (op == 'R') {
int x; char d; cin >> x >> d;
tr.assign(x+1, d);
} else { // if (op == 'I')
int x; char d; cin >> x >> d;
tr.insert(x+1, d), n++;
}
}
return 0;
}