题目大意：定义LCQ为从x,y分别开始，有多长完全一样。维护数据结构，给出xy，求出LCQ。此外还有修改和插入字符。
思路：LCQ一定是Hash＋二分，那么插入和修改呢，当然就是用Splay维护了。Splay上的每个节点存当前位置的字符，和它和整个子树的Hash值，重要是PushUp函数。除了维护子树大小，还需要维护Hash值。
与正常计算Hash值的方法一样，更新的根节点的Hash值可以表示为 Hash = ls->Hash + 27 ^ ls->size * Hash(root) + 27 ^ (ls->size + 1) * rs->Hash
详见代码。
CODE；
#include
#include
#include
#include
#define MAX 100010 using namespace std; unsigned long long power[MAX]; struct Complex{ char c; int size; unsigned long long hash; Complex *son[2],*father; void Combine(Complex *a,bool dir) { son[dir] = a; a->father = this; } bool Check() { return father->son[1] == this; } void PushUp() { size = son[0]->size + son[1]->size + 1; hash = son[0]->hash + (c - 'a' + 1) * power[son[0]->size] + son[1]->hash * power[son[0]->size + 1]; } }*nil = new Complex,*root; char s[MAX]; int asks; void Pretreatment(); Complex *BuildTree(int l,int r); Complex *NewComplex(char _); Complex *Kth(Complex *a,int k); inline void Rotate(Complex *a,bool dir); inline void Splay(Complex *a,Complex *aim); inline void SplaySeg(int x,int y); int main() { Pretreatment(); scanf("%s",s + 1); int length = (int)strlen(s + 1); root = BuildTree(0,length + 1); root->father = nil; cin >> asks; for(int x,y,i = 1;i <= asks; ++i) { scanf("%s",s); if(s[0] == 'Q') { scanf("%d%d",&x,&y); if(x > y) swap(x,y); int l = 0,r = root->size - 2 - y + 1,ans = 0; while(l <= r) { int mid = (l + r) >> 1; SplaySeg(x,x + mid - 1); unsigned long long hash1 = root->son[1]->son[0]->hash; SplaySeg(y,y + mid - 1); unsigned long long hash2 = root->son[1]->son[0]->hash; if(hash1 == hash2) ans = mid,l = mid + 1; else r = mid - 1; } printf("%d\n",ans); } else if(s[0] == 'R') { scanf("%d%s",&x,s); Splay(Kth(root,x + 1),nil); root->c = s[0]; root->PushUp(); } else { scanf("%d%s",&x,s); Splay(Kth(root,x + 1),nil); Splay(Kth(root,x + 2),root); root->son[1]->Combine(NewComplex(s[0]),false); root->son[1]->PushUp(); root->PushUp(); } } return 0; } void Pretreatment() { nil->son[0] = nil->son[1] = nil->father = nil; nil->hash = 0; power[0] = 1; for(int i = 1;i < MAX; ++i) power[i] = power[i - 1] * 27; } Complex *BuildTree(int l,int r) { if(l > r) return nil; int mid = (l + r) >> 1; Complex *re = NewComplex(s[mid]); re->Combine(BuildTree(l,mid - 1),false); re->Combine(BuildTree(mid + 1,r),true); re->PushUp(); return re; } Complex *NewComplex(char _) { Complex *re = new Complex(); re->c = _; re->son[0] = re->son[1] = nil; re->hash = _ - 'a' + 1; re->size = 1; return re; } Complex *Kth(Complex *a,int k) { if(k <= a->son[0]->size) return Kth(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; return Kth(a->son[1],k - 1); } inline void Rotate(Complex *a,bool dir) { Complex *f = a->father; f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; f->PushUp(); if(root == f) root = a; } inline void Splay(Complex *a,Complex *aim) { while(a->father != aim) { if(a->father->father == aim) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) Rotate(a->father,true),Rotate(a,true); else Rotate(a,false),Rotate(a,true); } else { if(a->Check()) Rotate(a->father,false),Rotate(a,false); else Rotate(a,true),Rotate(a,false); } } a->PushUp(); } inline void SplaySeg(int x,int y) { x++,y++; Splay(Kth(root,x - 1),nil); Splay(Kth(root,y + 1),root); }