BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)

// 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;
}
/*
*/