题意：
动态维护两后缀的最长公共前缀，要支持单点修改，单点插入。
分析：
本来以为要用什么后缀数据结构。。。结果想了半天无果。
才发现这题可以直接字符串hash+Splay水过。。。
真是傻了。。。Splay具体操作就是一般的序列Splay。。。每个点维护一个hash值表示它的子树的hash值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef unsigned long long ull;
ull fsp[MAXN];
int cnt;
struct node *NIL;
struct node{node *ch[2],*fa;ull hash,val;int siz;bool Dir(){return this==fa->ch[1];}void Setchild(node *x,int d){ch[d]=x;if(x!=NIL)x->fa=this; }void pushup(){siz=ch[0]->siz+ch[1]->siz+1;hash=ch[0]->hash+val*fsp[ch[0]->siz]+ch[1]->hash*fsp[ch[0]->siz+1];}
}tree[MAXN],*root,*ncnt;
node * Newnode(ull val){node *p=++ncnt;p->hash=val;p->siz=1;p->val=val;p->ch[0]=p->ch[1]=p->fa=NIL;return p;
}
void Rotate(node *x){int d=x->Dir();node *y=x->fa;if(y==root){root=x;x->fa=NIL; }elsey->fa->Setchild(x,y->Dir());y->Setchild(x->ch[!d],d);x->Setchild(y,!d);y->pushup();
}
void Splay(node *x,node *rt){//x->pushdown();while(x->fa!=rt){node *y=x->fa;if(y->fa==rt)Rotate(x);else{if(x->Dir()==y->Dir())Rotate(y);elseRotate(x);Rotate(x);}}x->pushup();
}
node *find_val(node *x,int val){if(x->ch[0]->siz>=val)return find_val(x->ch[0],val);val-=x->ch[0]->siz;if(val==1)return x;return find_val(x->ch[1],val-1);
}
node* find_nxt(node *x,int d){while(x->ch[d]!=NIL)x=x->ch[d];return x;
}
void Ins(int pos,int val){node *x=find_val(root,pos+1);Splay(x,NIL);node *y=find_nxt(x->ch[1],0);if(y==NIL){x->Setchild(Newnode(val),1); return ;}Splay(y,x);node *z=Newnode(val);z->Setchild(x->ch[1],1);x->Setchild(z,1);z->pushup();x->pushup();
}
void Change(int pos,int val){node *x=find_val(root,pos+1);Splay(x,NIL);x->val=val;x->pushup();
}
bool check(int len,int pl,int pr){node *x,*y;ull hash1,hash2;x=find_val(root,pl);Splay(x,NIL);y=find_val(x->ch[1],len+1);Splay(y,x);hash1=y->ch[0]->hash;//PF("[%d %llu ",len,hash1);x=find_val(root,pr);Splay(x,NIL);y=find_val(x->ch[1],len+1);Splay(y,x);hash2=y->ch[0]->hash;//PF("%llu]\n",hash2);return hash1==hash2;
}
int Que(int pl,int pr){int l=1,r=cnt-pr+1;int ans=0;while(l<=r){//PF("{
%d %d}\n",l,r);int mid=(l+r)>>1;if(check(mid,pl,pr)==1){ans=mid;l=mid+1;}elser=mid-1;}return ans;
}char s[MAXN];
node* build(int l,int r){if(l==r){node *x=Newnode(s[l]-'a'+1);return x;}int mid=(l+r)>>1;node *x=Newnode(s[mid]-'a'+1);if(l<mid)x->Setchild(build(l,mid-1),0);if(mid<r)x->Setchild(build(mid+1,r),1);x->pushup();return x;
}
void init(){NIL=&tree[0];NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;ncnt=&tree[0];
}
void Debug(node *x){if(x==NIL)return ;Debug(x->ch[0]);PF("%c",x->val-1+'a');Debug(x->ch[1]);
}
int main(){init();fsp[0]=1;for(int i=1;i<=100000;i++)fsp[i]=fsp[i-1]*131ull;SF("%s",s+2);int n=strlen(s+2);cnt=n;s[1]='a';s[n+2]='a';root=build(1,n+2);//Debug(root);int q,u,v;SF("%d",&q);while(q--){SF("%s",s);if(s[0]=='Q'){SF("%d%d",&u,&v);if(u>v)swap(u,v);PF("%d\n",Que(u,v));}else if(s[0]=='R'){SF("%d",&u);SF("%s",s);Change(u,s[0]-'a'+1);}else{cnt++;SF("%d",&u);SF("%s",s);Ins(u,s[0]-'a'+1);}//Debug(root);}
}