题面
题解
首先，我们知道求最长公共前缀可以用二分答案+hash来求
因为有修改操作， 考虑将整个字符串的hash值放入splay中
接着就是splay的基本操作了
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
const int N = 500010;
typedef unsigned long long ull;
using namespace std;
inline int gi() {
RG int x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
return f ? -x : x;
}
ull p[N];
int tot;
struct Splay {
int fa, ch[2], siz, v;
ull hs;
}t[N];
int rt;
#define get(x) (t[t[x].fa].ch[1] == x)
#define ls t[x].ch[0]
#define rs t[x].ch[1]
inline void pushup(int x) {
t[x].siz = t[ls].siz + t[rs].siz + 1;
t[x].hs = t[rs].hs + (ull)t[x].v*p[t[rs].siz] + t[ls].hs*p[t[rs].siz+1];
}
void build(int l, int r, int x) {
if (l > r) return ;
int mid = (l + r) >> 1;
if (mid >= x) rs = mid;
else ls = mid;
t[mid].fa = x, t[mid].siz = 1;
if (l == r) return ;
build(l, mid-1, mid), build(mid+1, r, mid);
pushup(mid);
return ;
}
void rotate(int x) {
int y = t[x].fa, z = t[y].fa, k = get(x);
t[x].fa = z; t[z].ch[get(y)] = x;
t[t[x].ch[k^1]].fa = y; t[y].ch[k] = t[x].ch[k^1];
t[y].fa = x; t[x].ch[k^1] = y;
pushup(y);
return ;
}
void splay(int x, int goal) {
while (t[x].fa != goal) {
int y = t[x].fa, z = t[y].fa;
if (z != goal)
(get(x)^get(y)) ? rotate(x) : rotate(y);
rotate(x);
}
pushup(x);
if (!goal) rt = x;
}
int kth(int k) {
int x = rt;
while (233) {
if (t[ls].siz+1 == k) return x;
if (t[ls].siz+1 < k) k -= (t[ls].siz+1), x = rs;
else x = ls;
}
}
ull get_hash(int l, int r) {
int x = kth(l), y = kth(r+2);
splay(x, 0); splay(y, rt);
return t[t[t[rt].ch[1]].ch[0]].hs;
}
char ch[N];
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
p[0] = 1;
for (int i = 1; i <= 300000; i++) p[i] = (ull)27*p[i-1];
scanf("%s", ch+1);
int n = strlen(ch+1);
for (int i = 2; i <= n+1; i++)
t[i].v = t[i].hs = ch[i-1]-'a'+1;
build(1, n+2, rt);
rt = (n+3) >> 1;
tot = n+2;
int T = gi();
while (T--) {
char s[5];
scanf("%s", s);
if (s[0] == 'Q') {
int x = gi(), y = gi();
if (x > y) swap(x, y);
int l = 1, r = tot-y-1;
while (l <= r) {
int mid = (l + r) >> 1;
if (get_hash(x, x+mid-1) == get_hash(y, y+mid-1))
l = mid+1;
else r = mid-1;
}
printf("%d
", l-1);
}
else if (s[0] == 'R') {
int x = gi();
scanf("%s", s);
splay(kth(x+1), 0);
t[rt].hs -= (ull)t[rt].v*p[t[t[rt].ch[1]].siz];
t[rt].v = s[0]-'a'+1;
t[rt].hs += (ull)t[rt].v*p[t[t[rt].ch[1]].siz];
}
else {
int x = gi();
scanf("%s", s);
int k1 = kth(x+1), k2 = kth(x+2);
splay(k1, 0); splay(k2, k1);
t[t[rt].ch[1]].ch[0] = ++tot;
t[tot].fa = t[rt].ch[1];
t[tot].v = t[tot].hs = s[0]-'a'+1;
splay(tot, 0);
}
}
return 0;
}