上个帖子

在最后一个数据点中，代码结尾处的 assert RE 了。但是题目里说了字符串长度 $L$ 自始至终都满足 $L \le 10^5$。

吐槽：2024/07/40 更新一组 hack。 7 月 40 号是什么东西……

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6;
const int MAXN = N + 5;

const ull BASE = 13331;
ull pw[MAXN];
void hash_init() {
    pw[0] = 1;
    rep(i, 1, N)
        pw[i] = pw[i-1] * BASE;
}

template<typename Val>
struct Splay {
    int fa[MAXN], siz[MAXN], tr[MAXN][2];
    Val val[MAXN];
    ull hsh[MAXN];
    int root, tot;
    int newNode() {
        return ++tot;
    }
    Splay() {
        root = 0;
        tot = 0;

        int l = newNode();
        int r = newNode();
        val[l] = '#', val[r] = '#';
        root = l;
        tr[l][1] = r;
        fa[r] = l;
        pushup(r);
        pushup(l);
    }
    void pushup(int u) {
        siz[u] = siz[tr[u][0]] + siz[tr[u][1]] + 1;

        int s = siz[tr[u][1]];
        hsh[u] = hsh[tr[u][0]] * pw[s + 1] + (val[u] - 'a' + 1) * pw[s] + hsh[tr[u][1]];
    }
    bool dir(int u) {
        return u == tr[fa[u]][1];
    }
    void rotate(int u) {
        int v = fa[u], w = fa[v];
        bool r = dir(u);

        tr[v][r] = tr[u][!r];
        tr[u][!r] = v;
        if (w) tr[w][dir(v)] = u;

        if (tr[v][r]) fa[tr[v][r]] = v;
        fa[v] = u;
        fa[u] = w;

        pushup(v), pushup(u);
    }
    void splay(int u, int target = 0) {
        while (fa[u] != target) {
            int v = fa[u];
            if (fa[v] != target)
                rotate(dir(u) == dir(v) ? v : u);
            rotate(u);
        }
        if (!target) root = u;
    }
    int kth(int x) {
        // 找到第 k 个元素所在的节点，并且不 splay
        int u = root;
        while (true) {
            if (x <= siz[tr[u][0]])
                u = tr[u][0];
            else {
                x -= siz[tr[u][0]] + 1;
                if (x <= 0)
                    return u;
                u = tr[u][1];
            }
        }
        return -1;
    }
    void insert(int x, Val k) {
        int u = kth(x), v = kth(x+1);
        splay(u);
        splay(v, u);
        int w = newNode();
        tr[v][0] = w;
        fa[w] = v;
        val[w] = k;
        splay(w);
    }
    void assign(int x, Val k) {
        int u = kth(x);
        splay(u);
        val[u] = k;
        pushup(u);
    }
    ull query_hash(int l, int r) {
        int u = kth(l-1), v = kth(r+1);
        splay(u);
        splay(v, u);
        return hsh[tr[v][0]];
    }

    void print(int u) {
        if (!u)
            return;
        print(tr[u][0]);
        cerr << val[u];
        print(tr[u][1]);
    }
    void print() {
        print(root);
        cerr << '\n';
    }
};

int n;
Splay<char> tr;

int LCP(int x, int y) {
    if (x > y) swap(x, y);
    int l = 0, r = n - y + 2, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (tr.query_hash(x, x + mid - 1) == tr.query_hash(y, y + mid - 1)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    return ans;
}

int main() { ios::sync_with_stdio(0); cin.tie(0);
    hash_init();

    string s; cin >> s; n = s.length();
    rep(i, 1, n)
        tr.insert(i, s[i-1]);

    int q; cin >> q; while (q--) {
        char op; cin >> op;
        if (op == 'Q') {
            int x, y; cin >> x >> y;
            cout << LCP(x+1, y+1) << '\n';
        } else if (op == 'R') {
            int x; char d; cin >> x >> d;
            tr.assign(x+1, d);
        } else { // if (op == 'I')
            int x; char d; cin >> x >> d;
            tr.insert(x+1, d), n++;
        }
    }

    assert(n <= 1e5); // HERE
    return 0;
}