这个操作十分的复杂
但是可以拿平衡树维护
直接二分答案然后用$hash$值判断即可
复杂度$O(10000 * log^2 n + n \log n)$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define ri register int
#define ull unsigned long long
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)
#define gc getchar
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
} inline char gcr() {
char c = gc();
while() {
if(c >= 'a' && c <= 'z') return c;
if(c >= 'A' && c <= 'Z') return c;
c = gc();
}
} const int sid = ;
const int sed = ; char s[sid];
int n, m, rt, at, bt, ct, dt, id;
int sz[sid], ls[sid], rs[sid], pri[sid];
ull wei[sid], sum[sid], val[sid]; inline int rand() {
static int seed = ;
return seed = (1ll * seed * ) % ;
} inline int newnode(char v) {
++ id;
val[id] = v; sz[id] = ;
pri[id] = rand(); sum[id] = v;
return id;
} inline void upd(int o) {
sz[o] = sz[ls[o]] + sz[rs[o]] + ;
sum[o] = sum[ls[o]] + sum[rs[o]] * wei[sz[ls[o]] + ];
sum[o] += val[o] * wei[sz[ls[o]] + ];
} inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(pri[x] > pri[y]) {
rs[x] = merge(rs[x], y);
upd(x); return x;
}
else {
ls[y] = merge(x, ls[y]);
upd(y); return y;
}
} inline void split(int o, int k, int &x, int &y) {
if(!o) { x = y = ; return; }
if(k <= sz[ls[o]]) y = o, split(ls[o], k, x, ls[o]);
else x = o, split(rs[o], k - sz[ls[o]] - , rs[o], y);
upd(o);
} inline ull getHash(int l, int r) {
split(rt, r, at, bt);
split(at, l - , ct, dt);
ull ret = sum[dt];
rt = merge(ct, merge(dt, bt));
return ret;
} inline bool check(int x, int y, int v) {
return getHash(x, x + v - ) == getHash(y, y + v - );
} int main() {
scanf("%s", s + );
n = strlen(s + ); wei[] = ;
rep(i, , ) wei[i] = wei[i - ] * sed;
rep(i, , n) rt = merge(rt, newnode(s[i])); m = read();
rep(i, , m) {
char c = gcr();
int x, y; char d;
if(c == 'Q') {
x = read(); y = read();
if(x > y) swap(x, y);
int l = , r = n - y + , ans = ;
while(l <= r) {
int mid = (l + r) >> ;
if(check(x, y, mid)) {
l = mid + , ans = mid;
printf("qaq -> %d\n", mid);
}
else r = mid - ;
}
printf("%d\n", ans);
}
else if(c == 'R') {
x = read(); d = gcr();
split(rt, x - , at, bt);
split(bt, , ct, dt);
rt = merge(at, merge(newnode(d), dt));
}
else if(c == 'I') {
n ++;
x = read(); d = gcr();
split(rt, x, at, bt);
rt = merge(at, merge(newnode(d), bt));
}
}
return ;
}