[JSOI2008] 火星人

 ?1 #include<cstdio> ?2 #include<cstring> ?3 #include<algorithm> ?4 #define empty 100002 ?5 #define id(x) (s[f[x]][1]==x) ?6 #define ull unsigned long long ?7 using namespace std; ?8 ??9 int m,len; 10 char str[100010]; 11 ull hp[100010],v[100010],sum[100010],sd=37; 12 int s[100010][2],f[100010],root,sz[100010]; 13 ?14 void pushup(int p) 15 { 16 ????sz[p]=sz[s[p][0]]+sz[s[p][1]]+1; 17 ????sum[p]=sum[s[p][0]]*hp[sz[s[p][1]]+1]+sum[s[p][1]]+v[p]*hp[sz[s[p][1]]]; 18 } 19 ?20 int build(int l,int r) 21 { 22 ????if(l>r)return empty; 23 ????int mid=(l+r)>>1; 24 ????s[mid][0]=build(l,mid-1); 25 ????s[mid][1]=build(mid+1,r); 26 ????if(s[mid][0]!=empty)f[s[mid][0]]=mid; 27 ????if(s[mid][1]!=empty)f[s[mid][1]]=mid; 28 ????v[mid]=str[mid]-‘a‘+1; 29 ????pushup(mid); 30 ????return mid; 31 } 32 ?33 void rotate(int p) 34 { 35 ????int fa=f[p]; 36 ????int k=id(p); 37 ????s[fa][k]=s[p][!k]; 38 ????s[p][!k]=fa; 39 ????s[f[fa]][id(fa)]=p; 40 ????f[p]=f[fa]; 41 ????f[s[fa][k]]=fa; 42 ????f[fa]=p; 43 ????pushup(fa); 44 ????pushup(p); 45 } 46 ?47 void splay(int p,int g) 48 { 49 ????while(f[p]!=g) 50 ????{ 51 ????????int fa=f[p]; 52 ????????if(f[fa]==g) 53 ????????{ 54 ????????????rotate(p); 55 ????????????break; 56 ????????} 57 ????????if(id(p)^id(fa))rotate(p); 58 ????????else rotate(fa); 59 ????????rotate(p); 60 ????} 61 ????if(g==empty)root=p; 62 } 63 ?64 int qpos(int p,int rk) 65 { 66 ????if(sz[s[p][0]]>=rk)return qpos(s[p][0],rk); 67 ????else if(sz[s[p][0]]+1==rk)return p; 68 ????else return qpos(s[p][1],rk-1-sz[s[p][0]]); 69 } 70 ?71 bool check(int x,int y,int nw) 72 { 73 ????if((x+nw>len)||(y+nw>len)) 74 ????????return false; 75 ????splay(qpos(root,x),empty); 76 ????splay(qpos(root,x+nw+1),root); 77 ????ull hx=sum[s[s[root][1]][0]]; 78 ????splay(qpos(root,y),empty); 79 ????splay(qpos(root,y+nw+1),root); 80 ????ull hy=sum[s[s[root][1]][0]]; 81 ????return (hx==hy); 82 } 83 ?84 void query() 85 { 86 ????int x,y; 87 ????scanf("%d%d",&x,&y); 88 ????int ans=0; 89 ????for(int i=20;i>=0;i--) 90 ????????if(check(x,y,ans|(1<<i)))ans|=(1<<i); 91 ????printf("%d\n",ans); 92 } 93 ?94 void repair() 95 { 96 ????char c[5]; 97 ????int x; 98 ????scanf("%d",&x); 99 ????scanf("%s",c+1);100 ????int tar=qpos(root,x+1);101 ????splay(tar,empty);102 ????v[root]=c[1]-‘a‘+1;103 ????pushup(root);104 }105 106 void in()107 {108 ????char c[5];109 ????int x;110 ????scanf("%d",&x);111 ????scanf("%s",c+1);112 ????splay(qpos(root,x+1),empty);113 ????splay(qpos(root,x+2),root);114 ????f[++len]=s[root][1];115 ????s[s[root][1]][0]=len;116 ????v[len]=sum[len]=c[1]-‘a‘+1;117 ????sz[len]=1;118 ????pushup(s[root][1]);119 ????pushup(root);120 }121 122 int main()123 {124 ????scanf("%s",str+1);125 ????len=strlen(str+1);126 ????hp[0]=1;127 ????for(int i=1;i<=100005;i++)hp[i]=hp[i-1]*sd;128 ????for(int i=0;i<=100001;i++)s[i][0]=s[i][1]=f[i]=empty;129 ????str[0]=str[++len]=‘a‘-1;130 ????root=build(0,len);131 ????scanf("%d",&m);132 ????while(m--)133 ????{134 ????????char op[5];135 ????????scanf("%s",op+1);136 ????????if(op[1]==‘Q‘)query();137 ????????if(op[1]==‘R‘)repair();138 ????????if(op[1]==‘I‘)in();139 ????}140 ????return 0;141 }