题意

题目链接

Sol

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

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

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

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#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;

}

/*

*/