[BZOJ1014] [JSOI2008]火星人prefix

 ?1 #include <cmath> ?2 #include <ctime> ?3 #include <cstdio> ?4 #include <cstring> ?5 #include <cstdlib> ?6 #include <iostream> ?7 #include <algorithm> ?8 # define maxn 100010 ?9 # define p 66191 10 using namespace std; 11 typedef unsigned long long ULL; 12 ULL px[maxn]; 13 void ot(){cout<<"***"<<endl;} 14 void fen(){cout<<"-----------------"<<endl;} 15 void beg(){px[0]=1; for(int i=1;i<=100000;i++) px[i]=px[i-1]*p;} 16 struct Treap{ 17 ????Treap* ch[2]; 18 ????ULL hs1,hs2; int key,size,val; char lt; 19 ????Treap(int v,char ss) 20 ????????{lt=ss; val=v;hs2=hs1=(ULL)ss; size=1; key=rand(); ch[0]=ch[1]=NULL;} 21 ????ULL HS(Treap* now){ 22 ????????return now?now->hs2:0; 23 ????} 24 ????int SZ(Treap *now){ 25 ????????return now?now->size:0; 26 ????} 27 ????void update(){ 28 ????????// cout<<HS(ch[0])<<" ?"<<hs1<<" ?"<<HS(ch[1])<<endl; 29 ????????size=1+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0); 30 ????????hs2=HS(ch[0])*px[SZ(ch[1])+1]+hs1*px[SZ(ch[1])]+HS(ch[1]); 31 ????} 32 }*root; 33 void ot_t(Treap* now){ 34 ????if(!now) return; 35 ????if(now->ch[0]) ot_t(now->ch[0]); 36 ????cout<<now->lt; 37 ????if(now->ch[1]) ot_t(now->ch[1]); 38 } 39 typedef pair<Treap*,Treap*> D; 40 int Size(Treap* now){return now?now->size:0;} 41 D Split(Treap* now,int k){ 42 ????if(!now) return D(NULL,NULL); 43 ????D y; 44 ????if(Size(now->ch[0])>=k) 45 ????????{y=Split(now->ch[0],k); now->ch[0]=y.second; now->update(); y.second=now;} 46 ????else 47 ????????{y=Split(now->ch[1],k-Size(now->ch[0])-1); now->ch[1]=y.first; now->update(); y.first=now;} 48 ????return y; 49 } 50 Treap* Merge(Treap *a,Treap* b){ 51 ????if(!a) return b; 52 ????if(!b) return a; 53 ????if(a->key<b->key) 54 ????????{a->ch[1]=Merge(a->ch[1],b); a->update(); return a;} 55 ????else 56 ????????{b->ch[0]=Merge(a,b->ch[0]); b->update(); return b;} 57 } 58 void Insert(int pos,char ss){ 59 ????D x=Split(root,pos); 60 ????Treap* now=new Treap(pos,ss); 61 ????root=Merge(Merge(x.first,now),x.second); 62 } 63 void change(int pos,char ss){ 64 ????D x=Split(root,pos-1); 65 ????D y=Split(x.second,1); 66 ????Treap* now=new Treap(pos,ss); 67 ????root=Merge(Merge(x.first,now),y.second); 68 } 69 char s[100010]; 70 int n; 71 bool check(int a1,int a2,int mid){ 72 ????if(!mid) return 1; 73 ????D x=Split(root,a1-1); 74 ????D y=Split(x.second,mid); 75 ????ULL now1=y.first->hs2; 76 ????root=Merge(Merge(x.first,y.first),y.second); 77 ????x=Split(root,a2-1); 78 ????y=Split(x.second,mid); 79 ????ULL now2=y.first->hs2; 80 ????root=Merge(Merge(x.first,y.first),y.second); 81 ????if(now1==now2) return 1; 82 ????return 0; 83 } 84 void find_ans(int x,int y,int len){ 85 ????int l=0,r=len-y+1,mid,ans; 86 ????while(l<=r){ 87 ????????mid=(l+r)>>1; 88 ????????if(check(x,y,mid)) ans=mid,l=mid+1; 89 ????????else r=mid-1; 90 ????} 91 ????printf("%d\n",ans); 92 } 93 void work(){ 94 ????scanf("%s",&s); 95 ????int len=strlen(s); 96 ????ULL h=0; 97 ????for(int i=0;i<len;i++){ 98 ????????Insert(i,s[i]); 99 ????}100 ????scanf("%d",&n);101 ????char od[3],ss; int x,y;102 ????for(int i=1;i<=n;i++){103 ????????scanf("%s",&od);104 ????????if(od[0]==‘Q‘){105 ????????????scanf("%d%d",&x,&y);106 ????????????find_ans(x,y,len);107 ????????}108 ????????else if(od[0]==‘I‘){109 ????????????scanf("%d%s",&x,&ss);110 ????????????Insert(x,ss); len++;111 ????????}112 ????????else{113 ????????????scanf("%d%s",&x,&ss);114 ????????????change(x,ss);115 ????????}116 ????}117 }118 int main(){119 ????// freopen("a.in","r",stdin);120 ????beg();121 ????work();122 ????return 0;123 }