用的fhq

#include <bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define __int32 int
#define __int64 long long
#define db long double
#define eps 1e-12
#define dbg1(s, v) cout << (s) << ": " << (v) << " "
#define dbg2(s, v) cout << (s) << ": " << (v) << "\n"
#define siz(i) tr[i].siz
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
#define id(i) tr[i].id
#define rnd(i) tr[i].rnd
#define lazy(i) tr[i].lazy
#define hsh(i) tr[i].hsh
#define chr(i) tr[i].chr
void Freopen() { freopen(".in", "r", stdin), freopen(".out", "w", stdout); }
const int N = 2e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;
const ull base = 137;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; ! isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x *= f;
}
void write( int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
using namespace std;
int n, m, tot, rt;
char s[N];
ull pw[N];
struct fhq {
	int rnd, ls, rs, id, siz, lazy;
	ull chr, hsh;
} tr[N];
int newnode( int id, ull ch) { return tr[++ tot] = {rand(), 0, 0, id, 1, 0, ch, 0}, tot; }
void print( int k) {
	if (! k) return ;
	printf("k = %d, ls = %d, rs = %d, chr = %llu\n", id(k), id(ls(k)), id(rs(k)), chr(k));
	print(ls(k)), print(rs(k));
}
void pushup( int k) {
	siz(k) = siz(ls(k)) + siz(rs(k)) + 1;
	hsh(k) = hsh(ls(k)) * pw[siz(rs(k)) + 1] + chr(k) * pw[siz(rs(k))] + hsh(rs(k));
//	print(k);
//	puts("");
}
void pushdown( int k) {
	if (! lazy(k)) return ;
	lazy(ls(k)) += lazy(k), lazy(rs(k)) += lazy(k);
	id(ls(k)) += lazy(k), id(rs(k)) += lazy(k);
	lazy(k) = 0;
}
int merge( int a, int b) {
	if (! a || ! b) return a + b;
	if (rnd(a) < rnd(b)) return pushdown(a), rs(a) = merge(rs(a), b), pushup(a), a;
	else return pushdown(b), ls(b) = merge(a, ls(b)), pushup(b), b;
}
void split( int k, int & a, int & b, int x) {
	if (! k) return a = b = 0, void();
	pushdown(k);
	if (id(k) <= x) a = k, split(rs(k), rs(a), b, x); else b = k, split(ls(k), a, ls(b), x);
	pushup(k);
}
void ins( int id, ull ch) {
	int x, y;
	split(rt, x, y, id - 1);
	if (y) lazy(y) += 1, id(y) += 1;
	rt = merge(merge(x, newnode(id, ch)), y);
}
signed main() {
//	srand(time(0));
	scanf("%s", s + 1), n = strlen(s + 1);
	pw[0] = 1;
	for ( int i = 1; i <= n; i ++) pw[i] = pw[i - 1] * base;
	for ( int i = 1; i <= n; i ++) ins(i, (ull)(s[i]));
//	print(rt);
	m = read();
	while (m --) {
		char op[5], d; int x, y; 
		scanf("%s", op), x = read();
		if (op[0] == 'Q') {
			y = read();
			int l = 0, r = min(n - x + 1, n - y + 1);
			while (l < r) {
				int mid = (l + r + 1) >> 1;
				int a, b, c;
				if (mid == 1) {
					split(rt, a, b, x - 1), split(b, b, c, x);
					ull res1 = chr(b);
//					printf("l = %d, r = %d, ch = %llu\n", x, x + mid - 1, res1);
					rt = merge(merge(a, b), c);
					split(rt, a, b, y - 1), split(b, b, c, y);
					ull res2 = chr(b);
//					printf("l = %d, r = %d, ch = %llu\n", y, y + mid - 1, res2);
					rt = merge(merge(a, b), c);					
					if (res1 != res2) r = mid - 1;
					else l = mid;
				} else {
				split(rt, a, b, x + mid - 1), split(a, a, c, x);
					ull res1 = hsh(c);
	//				printf("l = %d, r = %d, hsh = %llu\n", x, x + mid - 1, res1);
					rt = merge(merge(a, c), b);
					split(rt, a, b, y + mid - 1), split(a, a, c, y);
					ull res2 = hsh(c);
	//				printf("l = %d, r = %d, hsh = %llu\n", y, y + mid - 1, res2);
					rt = merge(merge(a, c), b);
					if (res1 != res2) r = mid - 1;
					else l = mid;					
				}	
			}
			write(l), puts("");
		} else if (op[0] == 'R') {
			cin >> d;
			int a, b, c;
			split(rt, a, b, x), split(a, a, c, x - 1);
			chr(c) = (ull)(d);
			rt = merge(merge(a, c), b);
		} else cin >> d, ins(x + 1, d);
	}
//	print(rt);
}