博客开更!!

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  5 using namespace std;
  6 #define MAXN 150000+100
  7 #define MO 9875321
  8 int root,n,m,base[MAXN],hash[MAXN],num[MAXN],to[MAXN][2],fa[MAXN],size[MAXN],tot=0;
  9 char s[MAXN];
 10 void Up(int x)
 11 {
 12     int L=to[x][0],R=to[x][1];
 13     size[x]=size[L]+size[R]+1;
 14     hash[x]=hash[L]+num[x]*base[size[L]]+hash[R]*base[size[L]+1];
 15 }
 16 void Rotate(int &rt,int x)
 17 {
 18     int y=fa[x],z=fa[y];
 19     if(y!=rt) to[z][to[z][1]==y]=x;
 20     else rt=x;
 21     fa[x]=z;fa[y]=x;
 22     int c=to[y][1]==x;fa[to[x][c^1]]=y;
 23     to[y][c]=to[x][c^1];to[x][c^1]=y;
 24       
 25     Up(y);Up(x);
 26 }
 27 void Splay(int &rt,int x)
 28 {
 29     while(x!=rt)
 30     {
 31         if(fa[x]!=rt) Rotate(rt,fa[x]);
 32         Rotate(rt,x);
 33     }
 34 }
 35 int Find(int rt,int rank)
 36 {
 37     if(size[to[rt][0]]+1==rank) return rt;
 38     if(size[to[rt][0]]>=rank) return Find(to[rt][0],rank);
 39     return Find(to[rt][1],rank-size[to[rt][0]]-1);
 40 }
 41 void vist(int rt)
 42 {
 43     if(rt==0) return ;
 44     cout<<rt<<' '<<to[rt][0]<<' '<<to[rt][1]<<' '<<size[rt]<<endl;
 45     vist(to[rt][0]);vist(to[rt][1]);
 46 }
 47 int Do(int x,int lenth)
 48 {
 49     int L=Find(root,x-1),R=Find(root,x+lenth);
 50     Splay(root,L);Splay(to[L][1],R);
 51     return hash[to[R][0]];
 52 }
 53 int Solve(int x,int y)
 54 {
 55     int L=0,R=min(n-x,n-y)+2;
 56     while(L<R)
 57     {
 58         int mid=(L+R)/2;
 59         if(Do(x,mid+1)==Do(y,mid+1)) L=mid+1;
 60         else R=mid;
 61     }
 62     return L;
 63 }
 64 void Build(int L,int R,int last)
 65 {
 66     if(L>R) return ;
 67     if(L==R)
 68     {
 69         tot++;
 70         hash[tot]=num[tot]=s[L];
 71         fa[tot]=last;size[tot]=1;
 72         return ;
 73     }
 74     int now=++tot;
 75     int mid=(L+R)/2;
 76     if(L<mid) {to[now][0]=tot+1; Build(L,mid-1,now); }
 77     if(mid+1<=R) {to[now][1]=tot+1; Build(mid+1,R,now); }
 78     num[now]=s[mid];fa[now]=last;
 79     Up(now);
 80 }
 81 int main()
 82 {
 83     base[0]=1;for(int i=1;i<=150000+10;i++) base[i]=base[i-1]*27;
 84     scanf("%s",s+2);
 85     n=strlen(s+2);s[1]=s[n+2]=0;
 86     root=tot+1;
 87     Build(1,n+2,0);
 88     cin>>m;
 89     while(m--)
 90     {
 91         getchar();char c=getchar();
 92         if(c=='Q')
 93         {
 94             int x,y;scanf("%d %d",&x,&y);
 95             printf("%d
",Solve(x+1,y+1));
 96         }
 97         else if(c=='R')
 98         {
 99             int x;char c;
100             scanf("%d",&x);getchar();c=getchar();
101             x=Find(root,x+1);
102             Splay(root,x);
103             num[x]=c;
104             Up(x);
105         }
106         else
107         {
108             int x;char c;
109             scanf("%d",&x);getchar();c=getchar();
110             x++;int tmp=Find(root,x);
111             Splay(root,tmp);
112             int tmp1=Find(root,x+1);
113             Splay(to[tmp][1],tmp1);
114             to[tmp1][0]=++tot;
115             num[tot]=c;
116             fa[tot]=tmp1;
117             Up(tot);Up(tmp1);Up(tmp);
118             n++;
119         }
120     }
121     return 0;
122 }