题目传送门(BZOJ)
>原文链接<

题解 :

维护一个数据结构, 支持插入, 修改, 查询从两个点开始的最长公共前缀.

一棵维护区间的Splay能很好的完成这个任务

插入与修改就是Splay的插入和修改, 查询的时候利用二分答案+Splay提出长度为$mid$的区间, 求哈希验证.

而对于哈希值的维护, 节点$p$的哈希值代表这个节点所有子区间字符串的哈希,

$h[p] = (h[ls]\times Base + val[p])\times Base^{siz[ls]}+h[ls]$

一个比较基础的维护哈希的合并的做法.

插入的时候记得累加整颗树的$size$

代码 :

#include <cstdio>#include <cstring>#include <iostream>#define ls ch[p][0]#define rs ch[p][1]using namespace std;#define ull unsigned long long#define get(x) (ch[f[x]][1]==x)const int N = 200000;const ull B = 1313131;int siz[N], f[N], ch[N][2], val[N], root, sz;char opt[5], s[N];ull h[N], mi[N];int n, m;inline void up(int p) { if(!p) return ; siz[p] = siz[ls] + siz[rs] + 1; h[p] = (h[ls]*B+val[p])*mi[siz[rs]]+h[rs];}void build(int l, int r, int fa, bool flg) { if(l > r) return; int p = (l+r) >> 1; ch[fa][flg] = p; val[p] = s[p-1]; f[p] = fa; siz[p] = r-l+1; build(l, p-1, p, 0); build(p+1, r, p, 1); up(p); }inline void rotate(int x) { int y = f[x], z = f[y], k = get(x); ch[y][k] = ch[x][!k], f[ch[y][k]] = y; ch[x][!k] = y, f[y] = x, f[x] = z; if(z) ch[z][ch[z][1]==y] = x; up(y), up(x); if(root == y) root = x;}inline void splay(int x, int y) { for(int fa; (fa = f[x]) != y; rotate(x)) { if(f[fa] != y) rotate(get(x) == get(fa) ? fa : x); }}inline int find(int x) { int p = root; while(1) { if(x <= siz[ls]) p = ls; else { x -= siz[ls]+1; if(!x) return p; p = rs; } }}inline ull getHash(int x, int p) { p += 2; x = find(x), p = find(p); splay(x, 0), splay(p, root); return h[ls];}inline int solve(int x, int y) { int l = 1, r = sz-max(x, y); while(l < r) { int mid = (l+r) >> 1; if(getHash(x, x+mid-1) == getHash(y, y+mid-1)) l = mid+1; else r = mid; } return --l;}inline void change(int x, char c) { x = find(x+1); splay(x, 0); val[x] = c; up(x);}inline void insert(int x, char c) { ++ x; int p = x+1; x = find(x), p = find(p); splay(x, 0); splay(p, root); ls = ++ sz; h[ls] = val[ls] = c; siz[ls] = 1; f[ls] = p; up(p), up(x);}int main() { scanf("%s%d", s+1, &m); n = strlen(s+1); mi[0] = 1; for(int i = 1; i < N; i ++ ) mi[i] = mi[i-1]*B; build(1, n+2, 0, 0); sz = n+2; root = (n+3) >> 1; for(int i = 1, x; i <= m; i ++ ) { scanf("%s%d", opt, &x); if(opt[0] == 'Q') { int y; scanf("%d", &y); printf("%d\n", solve(x, y)); } else if(opt[0] == 'R') { scanf("%s", opt); change(x, opt[0]); } else { scanf("%s", opt); insert(x, opt[0]); } }}