题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1014
因为涉及到增加和修改，所以后缀数组就被pass掉了，想到的就是平衡树维护hash值，查询的时候就是二分相同的长度来比较，修改就是删除再增加。
这里使用的是无旋Treap
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int ull;
const int maxn = ;
int Siz[maxn], ls[maxn], rs[maxn], pos[maxn], val[maxn], root, cnt;
ull Hash[maxn], w[maxn];
inline void up(int x) {
Siz[x] = Siz[ls[x]] + Siz[rs[x]] + ;
w[x] = w[ls[x]] * Hash[Siz[rs[x]] + ] + Hash[Siz[rs[x]]] * val[x] + w[rs[x]];
}
inline void split_size(int x, int siz, int &A, int &B) {
if (x == )return (void)(A = B = );
if (siz <= Siz[ls[x]])
B = x, split_size(ls[x], siz, A, ls[x]);
else
A = x, split_size(rs[x], siz - Siz[ls[x]] - , rs[x], B);
up(x);
}
inline int Merge(int A, int B) {
if (A == || B == )return A | B;
int ans;
if (pos[A] > pos[B])ans = A, rs[A] = Merge(rs[A], B);
else ans = B, ls[B] = Merge(A, ls[B]);
up(ans);
return ans;
}
inline void insert(int x, char v) {
int A, B;
split_size(root, x, A, B);
cnt++;
w[cnt] = val[cnt] = v - 'a' + ;
Siz[cnt] = ;
pos[cnt] = rand();
root = Merge(Merge(A, cnt), B);
}
inline void Delete(int x) {
int A, B, C, D;
split_size(root, x, A, B);
split_size(A, x - , C, D);
D = Merge(ls[D], rs[D]);
root = Merge(Merge(C, D), B);
}
inline ull query(int l, int r) {
int A, B, C, D;
ull ans;
split_size(root, l - , A, B);
split_size(B, r - l + , C, D);
ans = w[C];
root = Merge(A, Merge(C, D));
return ans;
}
inline bool check(int x, int y, int len) {
return query(x, x + len - ) == query(y, y + len - );
}
inline int read() {
int x = , f = ; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -;
for (; isdigit(c); c = getchar()) x = x * + c - ''; return x * f;
}
inline char cread() {
char c = getchar();
for (; !isalpha(c); c = getchar()); return c;
}
inline void reads(string& s) {
char c = getchar();
for (; !isalpha(c); c = getchar()); s = " ";
for (; isalpha(c); c = getchar()) s += c;
}
string s;
int main() {
reads(s);
int n = s.size() - , m;
m = read();
Hash[] = ;
for (int i = ; i < maxn; i++)
Hash[i] = Hash[i - ] * ;
for (int i = ; i <= n; i++)
insert(i, s[i]);
while (m--) {
char opt;
int x, y;
opt = cread();
if (opt == 'Q') {
x = read(), y = read();
int l = , r = min(n - x, n - y) + , ans;
while (l <= r) {
int mid = l + r >> ;
if (check(x, y, mid)) {
ans = mid;
l = mid + ;
}
else
r = mid - ;
}
printf("%d\n", ans);
}
else if (opt == 'R') {
x = read(), opt = cread();
Delete(x);
insert(x - , opt);
}
else {
x = read(), opt = cread();
n++;
insert(x, opt);
}
}
return ;
}