P4036 火星人

真的不知道为什么了。挑不出来，写了差不多1.5h了吧

#include <bits/stdc++.h>
#define int long long
using ull = unsigned long long;
const ull base = 29;
const int N = 1e6;
char str[N];
ull m, n, Base[N];
void Hash(char *str)
{
    int n = strlen(str + 1);
    Base[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        Base[i] = Base[i - 1] * base;
    }
    return void();
}
std::mt19937 Rnd(std::chrono::_V2::steady_clock::now().time_since_epoch().count());
struct node 
{
    node *ls, *rs;
    int rnd, size, hash, val;
    node (int x = 0) {
        ls = rs = nullptr;
        rnd = Rnd(), size = 1, hash = 0, val = x;
    }
} ;
node *root;
#define lc u->ls
#define rc u->rs
#define size(x) (x ? x->size : 0)
#define hsh(x) (x ? x->hash : 0)
bool Check(node *u) { return u != nullptr; }
void Update(node *u)
{
    if (!Check(u)) return;
    u->size = size(lc) + size(rc) + 1;
    u->hash = hsh(lc) * Base[size(rc) + 1] + u->val * Base[size(rc) + 1] + hsh(rc);
}
node *merge(node *L, node *R)
{
    if (!L || !R)
        return L ? L : R;
    if (L->rnd > R->rnd)
    {
        L->rs = merge(L->rs, R);
        Update(L);
        return L;
    }
    else
    {
        R->ls = merge(L, R->ls);
        Update(R);
        return R;
    }
}
void split(node *u, int x, node *&L, node *&R)
{
    if (u == nullptr) return L = R = nullptr, void();
    int less = size(lc) + 1;
    if (x >= less) {
        L = u;
        split(u->rs, x - less, u->rs, R);
    } else {
        R = u;
        split(u->ls, x, L, u->ls);
    }
    Update(u);
}
ull get_hash(int l, int r)
{
    node *x, *y, *z;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    ull res = hsh(y);
    root = merge(merge(x, y), z);
    return res;
}
void modify(int id, char ch) 
{
    node *x, *y, *z;
    int val = ch - 'a' + 1, pos = id;
    split(root, pos - 1, x, z);
    split(z, 1, y, z);
    y->hash = y->val = val;
    root = merge(merge(x, y), z);
}
void insert(int id, char ch)
{
    node *x, *y;
    int val = ch - 'a' + 1, pos = id;
    split(root, pos, x, y);
    root = merge(x, merge(new node(val), y));
}
int LCP(int x, int y)
{
    if (x > y) std::swap(x, y);
    int l = 1, r = size(root) - y + 1, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (get_hash(x, x + mid - 1) == get_hash(y, y + mid - 1)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}
auto main() -> signed
{
    std::cin >> (str + 1);
    std::cin >> m;
    Hash(str);
    int len = strlen(str + 1);
    for (int i = 1; i <= len; i ++ ) {
        root = merge(root, new node(str[i] - 'a' + 1));
    }
    while (m -- )
    {
        char op, d;
        int x, y;
        std::cin >> op >> x;
        if (op == 'Q') {
            std::cin >> y;
            std::cout << LCP(x, y) << std::endl;
        } else if (op == 'R') {
            std::cin >> d;
            modify(x, d);      
        } else {
            std::cin >> d;
            insert(x, d);
        }
    }
    return 0;
}