luoguP4036 [JSOI2008]火星人 平衡树+hash

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define ri register int#define ull unsigned long long#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)#define drep(io, ed, st) for(ri io = ed; io >= st; io --)#define gc getcharinline int read() { ???int p = 0, w = 1; char c = gc(); ???while(c > ‘9‘ || c < ‘0‘) { if(c == ‘-‘) w = -1; c = gc(); } ???while(c >= ‘0‘ && c <= ‘9‘) p = p * 10 + c - ‘0‘, c = gc(); ???return p * w;}inline char gcr() { ???char c = gc(); ???while(1) { ???????if(c >= ‘a‘ && c <= ‘z‘) return c; ???????if(c >= ‘A‘ && c <= ‘Z‘) return c; ???????c = gc(); ???}}const int sid = 300005;const int sed = 19260817;char s[sid];int n, m, rt, at, bt, ct, dt, id;int sz[sid], ls[sid], rs[sid], pri[sid];ull wei[sid], sum[sid], val[sid];inline int rand() { ???static int seed = 14123; ???return seed = (1ll * seed * 1919) % 2147483647;}inline int newnode(char v) { ???++ id; ???val[id] = v; sz[id] = 1; ???pri[id] = rand(); sum[id] = v; ???return id;}inline void upd(int o) { ???sz[o] = sz[ls[o]] + sz[rs[o]] + 1; ???sum[o] = sum[ls[o]] + sum[rs[o]] * wei[sz[ls[o]] + 1]; ???sum[o] += val[o] * wei[sz[ls[o]] + 1];}inline int merge(int x, int y) { ???if(!x || !y) return x + y; ???if(pri[x] > pri[y]) { ???????rs[x] = merge(rs[x], y); ???????upd(x); return x; ???} ???else { ???????ls[y] = merge(x, ls[y]); ???????upd(y); return y; ???}}inline void split(int o, int k, int &x, int &y) { ???if(!o) { x = y = 0; return; } ???if(k <= sz[ls[o]]) y = o, split(ls[o], k, x, ls[o]); ???else x = o, split(rs[o], k - sz[ls[o]] - 1, rs[o], y); ???upd(o);}inline ull getHash(int l, int r) { ???split(rt, r, at, bt); ???split(at, l - 1, ct, dt); ???ull ret = sum[dt]; ???rt = merge(ct, merge(dt, bt)); ???return ret;}inline bool check(int x, int y, int v) { ???return getHash(x, x + v - 1) == getHash(y, y + v - 1);}int main() { ???scanf("%s", s + 1); ???n = strlen(s + 1); ???????wei[0] = 1; ???rep(i, 1, 300000) wei[i] = wei[i - 1] * sed; ???rep(i, 1, n) rt = merge(rt, newnode(s[i])); ???????????m = read(); ???rep(i, 1, m) { ???????char c = gcr(); ???????int x, y; char d; ???????if(c == ‘Q‘) { ???????????x = read(); y = read(); ???????????if(x > y) swap(x, y); ???????????int l = 1, r = n - y + 1, ans = 0; ???????????while(l <= r) { ???????????????int mid = (l + r) >> 1; ???????????????if(check(x, y, mid)) { ???????????????????l = mid + 1, ans = mid; ???????????????????printf("qaq -> %d\n", mid); ???????????????} ???????????????else r = mid - 1; ???????????} ???????????printf("%d\n", ans); ???????} ???????else if(c == ‘R‘) { ???????????x = read(); d = gcr(); ???????????split(rt, x - 1, at, bt); ???????????split(bt, 1, ct, dt); ???????????rt = merge(at, merge(newnode(d), dt)); ???????} ???????else if(c == ‘I‘) { ???????????n ++; ???????????x = read(); d = gcr(); ???????????split(rt, x, at, bt); ???????????rt = merge(at, merge(newnode(d), bt)); ???????} ???} ???return 0;}