bzoj 1014 [JSOI2008]火星人prefix (splay+二分答案+字符串hash)

 ?1 #include <cstdio> ?2 #include <cstring> ?3 #include <algorithm> ?4 #define il inline ?5 #define ui unsigned int ???6 #define ull unsigned long long ??7 #define seed 13131 ?8 #define N 110000 ?9 #define root d[0].ch[1] 10 using namespace std; 11 ?12 char str[N],Q[10],q[10]; 13 ull pw[N]; 14 int n,m,tot; 15 struct SPLAY{int fa,ch[2],sz;ull hsh,val;}d[N]; 16 int gc() 17 { 18 ????int rett=0,fh=1;char p=getchar(); 19 ????while(p<‘0‘||p>‘9‘){if(p==‘-‘)fh=-1;p=getchar();} 20 ????while(p>=‘0‘&&p<=‘9‘){rett=(rett<<3)+(rett<<1)+p-‘0‘;p=getchar();} 21 ????return rett*fh; 22 } 23 il ull idx(char c){return c-‘a‘+1;} 24 il void con(int x,int ff,int p){d[x].fa=ff,d[ff].ch[p]=x;} 25 il int idf(int x){return d[d[x].fa].ch[0]==x?0:1;} 26 il int cre(ull w){tot++;d[tot].val=w,d[tot].sz=1,d[tot].hsh=w;return tot;} 27 il void pushup(int x) 28 { 29 ????d[x].sz=d[d[x].ch[0]].sz+d[d[x].ch[1]].sz+1; 30 ????d[x].hsh=d[d[x].ch[0]].hsh*pw[d[d[x].ch[1]].sz+1]+(ull)d[x].val*pw[d[d[x].ch[1]].sz]+d[d[x].ch[1]].hsh; 31 } 32 il void rot(int x) 33 { 34 ????int y=d[x].fa;int ff=d[y].fa;int px=idf(x);int py=idf(y); 35 ????con(d[x].ch[px^1],y,px),con(y,x,px^1),con(x,ff,py); 36 ????pushup(y),pushup(x); 37 } 38 void splay(int x,int to) 39 { 40 ????to=d[to].fa; 41 ????while(d[x].fa!=to){ 42 ????????int y=d[x].fa; 43 ????????if(d[y].fa==to) rot(x); 44 ????????else if(idf(x)==idf(y)){rot(y);rot(x);} 45 ????????else{rot(x);rot(x);} 46 ????} 47 } 48 int build(int l,int r,int ff) 49 { 50 ????if(l>r) return 0; 51 ????int mid=(l+r)>>1; 52 ????int pos=cre(idx(str[mid])); 53 ????d[pos].fa=ff; 54 ????d[pos].ch[0]=build(l,mid-1,pos); 55 ????d[pos].ch[1]=build(mid+1,r,pos); 56 ????pushup(pos); 57 ????return pos; 58 } 59 int find_pos(int pos) 60 { 61 ????int x=root; 62 ????while(x) 63 ????{ 64 ????????if(d[d[x].ch[0]].sz>=pos) x=d[x].ch[0]; 65 ????????else{ 66 ????????????pos-=d[d[x].ch[0]].sz; 67 ????????????if(pos==1) return x; 68 ????????????pos--,x=d[x].ch[1]; 69 ????????} 70 ????} 71 ????return x; 72 } 73 void ins(int pos,ull w) 74 { 75 ????int ff=find_pos(pos+1),x,y;splay(ff,root); 76 ????if(!d[ff].ch[1]) ?77 ????????x=cre(w),con(x,ff,1),pushup(ff); 78 ????else{ 79 ????????x=d[ff].ch[1]; 80 ????????while(x) 81 ????????????if(d[x].ch[0]) x=d[x].ch[0]; 82 ????????????else break; 83 ????????y=cre(w),con(y,x,0),pushup(x); 84 ????????splay(x,root); 85 ????} 86 } 87 void replac(int pos,ull w) 88 { 89 ????int x=find_pos(pos+1);splay(x,root); 90 ????d[x].val=w;pushup(x); 91 } 92 il ull get_hsh(int pos) 93 { 94 ????int x=find_pos(pos); 95 ????splay(x,root); 96 ????int y=find_pos(n+2); 97 ????splay(y,d[x].ch[1]); 98 ????return d[d[d[x].ch[1]].ch[0]].hsh; 99 }100 il int check(int x,int y,int mid)101 {102 ????ull s1=0,s2=0,s3=0,s4=0;103 ????s1=get_hsh(x);104 ????if(x+mid<=n) s2=get_hsh(x+mid);105 ????s3=get_hsh(y);106 ????if(y+mid<=n) s4=get_hsh(y+mid);107 ????return (s1-s2==(s3-s4)*pw[y-x])?1:0;108 }109 int Query(int a,int b)110 {111 ????if(a>b){int t=a;a=b;b=t;}112 ????int l=1,r=n-b+1,ans=0;113 ????while(l<=r){114 ????????int mid=(l+r)>>1;115 ????????if(check(a,b,mid)) ans=mid,l=mid+1;116 ????????else r=mid-1;117 ????}118 ????return ans;119 }120 void stt()121 {122 ????n=strlen(str+1);pw[0]=1;123 ????for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*seed;124 ????int x=cre(0),y=cre(0),z;125 ????con(x,0,1),con(y,1,1);126 ????z=build(1,n,y);127 ????con(z,y,0);128 ????pushup(y),pushup(x);129 }130 131 int main()132 {133 ????scanf("%s",str+1);134 ????stt();135 ????scanf("%d",&m);136 ????int x,y;137 ????for(int i=1;i<=m;i++)138 ????{139 ????????scanf("%s",Q);140 ????????if(Q[0]==‘Q‘){141 ????????????x=gc(),y=gc();142 ????????????printf("%d\n",Query(x,y));143 ????????}else if(Q[0]==‘I‘){144 ????????????x=gc();scanf("%s",q);145 ????????????ins(x,idx(q[0]));146 ????????????n++;147 ????????}else{148 ????????????x=gc();scanf("%s",q);149 ????????????replac(x,idx(q[0]));150 ????????}151 ????}152 ????return 0;153 }