题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1014
先考虑如果没有修改操作和插入操作，是一个静态的字符串，我们可以怎样快速求得题目中的LCQ。
两个字符串判等很容易想到hash。于是我们二分答案并二分判断，就可以在$log_n$时间内得到答案。
现在加上修改和插入操作，其实就是要动态维护子串也就是一段区间的hash值，这种问题很容易就想到用splay来维护。
每个节点记录此节点管辖下子树的hash值h，当前节点的h=左孩子的h+节点的值*seed^{左孩子的size}+右孩子*seed^{左孩子的size+1}
提取子串的hash值就是$log_n$的，时间复杂度$O(nlog_n^2)$
?1 #include<cstdio> ?2 #include<cstring> ?3 #include<algorithm> ?4 using namespace std; ?5 typedef long long ll; ?6 const ll seed=233; ?7 int inline readint(){ ?8 ????int Num;char ch; ?9 ????while((ch=getchar())<‘0‘||ch>‘9‘);Num=ch-‘0‘; 10 ????while((ch=getchar())>=‘0‘&&ch<=‘9‘) Num=Num*10+ch-‘0‘; 11 ????return Num; 12 } 13 void outint(int x){ 14 ????if(x>=10) outint(x/10); 15 ????putchar(x%10+‘0‘); 16 } 17 int ch[100010][2],fa[100010],siz[100010],cnt=0,Rt=0,len=0; 18 char val[100010]; 19 ll h[100010],pow[100010]; 20 void Pushup(int &rt){ 21 ????siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1; 22 ????h[rt]=h[ch[rt][0]]+val[rt]*pow[siz[ch[rt][0]]]+h[ch[rt][1]]*pow[siz[ch[rt][0]]+1]; 23 } 24 int Rot(int x,int p){ 25 ????int y=fa[x],z=fa[y]; 26 ????fa[ch[x][!p]]=y;ch[y][p]=ch[x][!p]; 27 ????fa[x]=z;if(z) ch[z][ch[z][1]==y]=x; 28 ????fa[y]=x;ch[x][!p]=y; 29 ????Pushup(y);Pushup(x); 30 } 31 void Splay(int x,int T){ 32 ????while(fa[x]!=T){ 33 ????????if(fa[fa[x]]==T) Rot(x,ch[fa[x]][1]==x); 34 ????????else{ 35 ????????????int y=fa[x],z=fa[y],p=ch[z][1]==y; 36 ????????????if(ch[y][p]==x) Rot(y,p),Rot(x,p); 37 ????????????else Rot(x,!p),Rot(x,p); 38 ????????} 39 ????} 40 ????if(!T) Rt=x; 41 } 42 void Find(int k,int t){ 43 ????int x=Rt,tmp; 44 ????while(x){ 45 ????????tmp=siz[ch[x][0]]; 46 ????????if(k==tmp+1){ 47 ????????????Splay(x,t); 48 ????????????return; 49 ????????} 50 ????????else if(k<tmp+1) x=ch[x][0]; 51 ????????else{ 52 ????????????k-=tmp+1; 53 ????????????x=ch[x][1]; 54 ????????} 55 ????} 56 } 57 char s[100010]; 58 int Build(int l,int r){ 59 ????if(l>r) return 0; 60 ????int mid=l+r>>1,rt=++cnt; 61 ????val[rt]=s[mid]; 62 ????ch[rt][0]=Build(l,mid-1); 63 ????if(ch[rt][0]) fa[ch[rt][0]]=rt; 64 ????ch[rt][1]=Build(mid+1,r); 65 ????if(ch[rt][1]) fa[ch[rt][1]]=rt; 66 ????Pushup(rt); 67 ????return rt; 68 } 69 void Lcq(int x,int y){ 70 ????int l=1,r=len,mid,ans=0; 71 ????ll tmp; 72 ????while(l<=r){ 73 ????????mid=l+r>>1; 74 ????????if(y+mid>len+1) r=mid-1; 75 ????????else{ 76 ????????????Find(x,0); 77 ????????????Find(x+mid+1,Rt); 78 ????????????tmp=h[ch[ch[Rt][1]][0]]; 79 ????????????Find(y,0); 80 ????????????Find(y+mid+1,Rt); 81 ????????????if(tmp==h[ch[ch[Rt][1]][0]]){ 82 ????????????????ans=mid; 83 ????????????????l=mid+1; 84 ????????????} 85 ????????????else r=mid-1; 86 ????????} 87 ????} 88 ????outint(ans); 89 ????putchar(‘\n‘); 90 } 91 int main(){ 92 ????pow[0]=1;for(int i=1;i<=100000;i++) pow[i]=pow[i-1]*seed; 93 ????siz[0]=h[0]=fa[0]=ch[0][0]=ch[0][1]=0; 94 ????scanf("%s",s+1); 95 ????len=strlen(s+1); 96 ????Rt=Build(0,len+1); 97 ????int m,x,y; 98 ????scanf("%d",&m); 99 ????char opt[5],tmp[5];100 ????while(m--){101 ????????scanf("%s",opt);102 ????????switch(opt[0]){103 ????????????case ‘R‘:104 ????????????????scanf("%d%s",&x,tmp);105 ????????????????Find(x+1,0);106 ????????????????val[Rt]=tmp[0];107 ????????????????Pushup(Rt);108 ????????????????break;109 ????????????case ‘I‘:110 ????????????????scanf("%d%s",&x,tmp);111 ????????????????Find(x+1,0);112 ????????????????Find(x+2,Rt);113 ????????????????val[++cnt]=tmp[0];114 ????????????????fa[cnt]=ch[Rt][1];115 ????????????????ch[ch[Rt][1]][0]=cnt;116 ????????????????Pushup(cnt);117 ????????????????Pushup(ch[Rt][1]);118 ????????????????Pushup(Rt);119 ????????????????len++;120 ????????????????break;121 ????????????case ‘Q‘:122 ????????????????scanf("%d%d",&x,&y);123 ????????????????if(x>y) swap(x,y);124 ????????????????Lcq(x,y);125 ????????????????break; 126 ????????}127 ????}128 }[BZOJ1014][JSOI2008]火星人prefix splay+hash+二分
原文地址：http://www.cnblogs.com/halfrot/p/7440153.html