题目链接：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
     
        2 #include
      
         3 #include
       
          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
        
         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 }