题意

Sol

一眼splay + 二分hash，不过区间splay怎么写来着呀

试着写了两个小时发现死活不对

看了一下yyb的代码发现自己根本就不会splay。。。。

// luogu-judger-enable-o2#include
    
     #define ull unsigned long long using namespace std;const int MAXN = 1e6 + 10;const ull base = 27;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, M;char s[MAXN];int root, tot, ch[MAXN][2], fa[MAXN], siz[MAXN];ull ha[MAXN], val[MAXN], po[MAXN];bool rev[MAXN];int ident(int x) {    return ch[fa[x]][1] == x;}void connect(int x, int f, int id) {    fa[x] = f; ch[f][id] = x;}void update(int x) {    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;    ha[x] = ha[ch[x][0]] + val[x] * po[siz[ch[x][0]]] + po[siz[ch[x][0]] + 1] * ha[ch[x][1]];}void rotate(int x) {    int y = fa[x], R = fa[y], Yson = ident(x), Rson = ident(y);    int B = ch[x][Yson ^ 1];    connect(x, R, Rson); connect(B, y, Yson); connect(y, x, Yson ^ 1);    update(y); update(x); }void splay(int x, int to) {    //to = fa[to];    while(fa[x] != to) {        if(fa[fa[x]] == to) rotate(x);        else if(ident(x) == ident(fa[x])) rotate(fa[x]), rotate(x);        else rotate(x), rotate(x);    }    if(!to) root = x; update(x);}int find(int k) {    int x = root;    while(1) {        if(siz[ch[x][0]] + 1 == k) return x;        if(siz[ch[x][0]] + 1 < k) k -= siz[ch[x][0]] + 1, x = ch[x][1];//tag        else x = ch[x][0];    }}ull gethash(int l, int len) {    int x = find(l), y = find(l + len + 1);    splay(x, 0); splay(y, x);     return ha[ch[y][0]];}int LCP(int y, int x) {    int l = 0, r = tot - max(x, y) - 1, ans = 0;    while(l <= r) {        int mid = l + r >> 1;        if(gethash(x, mid) == gethash(y, mid)) l = mid + 1, ans = mid;        else r = mid - 1;    }    return ans;}void insert(int x, int v) {    int l = find(x + 1), r = find(x + 2);    splay(l, 0); splay(r, l);    val[++tot] = v; fa[tot] = r; ch[r][0] = tot; splay(tot, 0); }void change(int x, int v) {    int l = find(x), r = find(x + 2);    splay(l, 0); splay(r, l);    val[ch[r][0]] = v; update(ch[r][0]);     update(r); update(l);}int main() {//  freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);    po[0] = 1;     for(int i = 1; i <= (int)1e5; i++) po[i] = base * po[i - 1];    scanf("%s", s + 1); N = strlen(s + 1);      ch[1][1] = 2; fa[2] = 1; tot = 2; root = 1; update(2); update(1);     for(int i = 1; i <= N; i++)         insert(i - 1, s[i]);    int M = read();    while(M--) {        char opt[3]; scanf("%s", opt);        if(opt[0] == 'Q') {int x = read(), y = read(); printf("%d\n", LCP(x, y));}        else if(opt[0] == 'R') {            int x = read(); scanf("%s", opt + 1);            change(x, opt[1]);        } else {            int x = read(); scanf("%s", opt + 1);            insert(x, opt[1]);         }    }    return 0;}/**/