只过了 #6 #7 #8

怎么今天做 fhq 做一道挂一道啊/ll

// Problem: P4036 [JSOI2008] 火星人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4036
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <cstring>
#include <ctime>
#include <iostream>

#define ull unsigned long long

using namespace std;

const int maxn = 1e6 + 10;
const ull base = 19260817;

ull pw[maxn];

int n;
char ch[maxn];

int RT, tot;
struct node {
    int ch[2];
    int siz, data;
    ull val;
    ull sum;
} t[maxn];
int newnode(int x)
{
    tot++;
    t[tot].ch[0] = t[tot].ch[1] = 0;
    t[tot].siz = 1;
    t[tot].data = rand();
    t[tot].sum = t[tot].val = (ull)x;
    return tot;
}
void pushup(int x)
{
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1;
    t[x].sum = 1ull * t[t[x].ch[0]].sum * pw[t[t[x].ch[1]].siz + 1] + 1ull * pw[t[t[x].ch[1]].siz] * t[x].val + 1ull * t[t[x].ch[1]].sum;
}
void split(int rt, int rk, int& x, int& y)
{
    if (!rt) {
        x = y = 0;
        return;
    }
    if (t[t[rt].ch[0]].siz + 1 <= rk)
        x = rt, split(t[rt].ch[1], rk - t[t[x].ch[0]].siz - 1, t[rt].ch[1], y);
    else
        y = rt, split(t[rt].ch[0], rk, x, t[rt].ch[0]);
    pushup(rt);
}
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (t[x].data < t[y].data) {
        t[x].ch[1] = merge(t[x].ch[1], y), pushup(x);
        return x;
    } else {
        t[y].ch[0] = merge(x, t[y].ch[0]), pushup(y);
        return y;
    }
}
ull get_hash(int l, int r)
{
    int a, b, c;
    split(RT, r, a, c);
    split(a, l - 1, a, b);
    ull ans = t[b].sum;
    RT = merge(merge(a, b), c);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    srand(time(0));

    pw[0] = 1;
    for (int i = 1; i < maxn; i++)
        pw[i] = pw[i - 1] * base;
    // for (int i = 1; i <= 10; i++)
    // cout << pw[i] << " ";
    // cout << "\n";
    cin >> (ch + 1);
    int len = strlen(ch + 1);
    for (int i = 1; i <= len; i++)
        RT = merge(RT, newnode(ch[i] - 'a'));
    // for (int i = 1; i <= len; i++)
    // cout << get_hash(i, len) << " ";
    cin >> n;
    while (n--) {
        char opt;
        cin >> opt;
        if (opt == 'Q') {
            int x, y;
            cin >> x >> y;
            int l = 1, r = min(len - x, len - y) + 1, ans = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                // cout << mid << " " << get_hash(x, x + mid - 1) << " " << get_hash(y, y + mid - 1) << "\n";
                if (get_hash(x, x + mid - 1) == get_hash(y, y + mid - 1))
                    ans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }
            cout << ans << "\n";
        } else if (opt == 'I') {
            int x;
            char c;
            cin >> x >> c;
            int a, b;
            split(RT, x, a, b);
            RT = merge(merge(a, newnode(c - 'a')), b);
        } else {
            int x;
            char c;
            cin >> x >> c;
            int a, b, p;
            split(RT, x, a, b);
            split(a, x - 1, a, p);
            RT = merge(merge(a, newnode(c - 'a')), b);
        }
    }
    return 0;
}