BZOJ-1014 ?[JSOI2008]火星人prefix (Splay+二分+hash)

 ?1 #include<iostream> ?2 #include<cstdlib> ?3 #include<cstdio> ?4 #include<cmath> ?5 #include<algorithm> ?6 #include<cstring> ?7 #include<queue> ?8 #include<vector> ?9 #include<set> 10 #define MAXN 500010 11 #define RG register 12 #define LL long long int 13 using namespace std; 14 const int INF=1e9; 15 const int mod=9875321; 16 int ch[MAXN][2],siz[MAXN],v[MAXN],ha[MAXN],fa[MAXN]; 17 int p[MAXN]; 18 int n,m,root,sz; 19 int val[MAXN]; 20 char s[MAXN]; 21 void up(int x) 22 { 23 ??int l=ch[x][0],r=ch[x][1]; 24 ??siz[x]=siz[l]+siz[r]+1; 25 ??ha[x]=(ha[l]+v[x]*p[siz[l]]%mod+(LL)ha[r]*p[siz[l]+1]%mod)%mod; 26 } 27 void build(int &k,int l,int r,int f) 28 { 29 ??if(l>r) return; 30 ??int mid=(l+r)>>1; 31 ??k=++sz;fa[k]=f;v[k]=val[mid]; 32 ??if(mid>l) build(ch[k][0],l,mid-1,k); 33 ??if(mid<r) build(ch[k][1],mid+1,r,k); 34 ??up(k); 35 } 36 void rotate(int x,int &k) 37 { 38 ??int old=fa[x],oldf=fa[old],rel=(ch[old][1]==x); 39 ??if(old==k) k=x; 40 ??else ch[oldf][ch[oldf][1]==old]=x; 41 ??fa[x]=oldf;fa[ch[x][rel^1]]=old;ch[old][rel]=ch[x][rel^1]; 42 ??fa[old]=x;ch[x][rel^1]=old; 43 ??up(old);up(x); 44 } 45 void splay(int x,int &k) 46 { 47 ??int old,oldf; 48 ??while(x!=k) 49 ????{ 50 ??????old=fa[x];oldf=fa[old]; 51 ??????if(old!=k) 52 ????{ 53 ??????if((ch[old][0]==x)^(ch[oldf][0]==old)) rotate(x,k); 54 ??????else rotate(old,k); 55 ????} 56 ??????rotate(x,k); 57 ????} 58 } 59 int find(int x) 60 { 61 ??int now=root; 62 ??while(1) 63 ????{ 64 ??????if(x<=siz[ch[now][0]]) now=ch[now][0]; 65 ??????else{ 66 ????if(x==siz[ch[now][0]]+1) return now; 67 ????x-=siz[ch[now][0]]+1;now=ch[now][1]; 68 ??????} 69 ????} 70 } 71 void change(int x,char d) 72 { 73 ??x=find(x);splay(x,root); 74 ??v[root]=d-‘a‘+1;up(root); 75 } 76 void insert(int x,char d) 77 { 78 ??int l=x,r=x+1; 79 ??l=find(l);r=find(r);splay(l,root);splay(r,ch[root][1]); 80 ??++sz;ch[r][0]=sz;v[sz]=d-‘a‘+1;fa[sz]=r;up(sz);up(r);up(l); 81 } 82 int get(int x,int y) 83 { 84 ??x=find(x-1);y=find(y+1); 85 ??splay(x,root);splay(y,ch[root][1]); 86 ??return ha[ch[y][0]]; 87 } 88 int solve(int x,int y) 89 { 90 ??int l=1,r=min(sz-x,sz-y),ans=0; 91 ??while(l<=r) 92 ????{ 93 ??????int mid=(l+r)>>1; 94 ??????if(get(x,x+mid-1)==get(y,y+mid-1)) ans=mid,l=mid+1; 95 ??????else r=mid-1; 96 ????} 97 ??return ans; 98 } 99 int main()100 {101 ??freopen("1.in","r",stdin);102 ??scanf("%s",s);n=strlen(s);p[0]=1;103 ??for(int i=1;i<=150010;i++) p[i]=p[i-1]*28%mod;104 ??for(int i=1;i<=n+2;i++) if(i==1 || i== n+2) val[i]=27; else val[i]=s[i-2]-‘a‘+1; 105 ??build(root,1,n+2,0);106 ??scanf("%d",&m);char op[3],d[3];int x,y;107 ??for(int i=1;i<=m;i++)108 ????{109 ??????scanf("%s%d",op,&x);x++;110 ??????if(op[0]==‘Q‘){111 ????scanf("%d",&y);y++;112 ????printf("%d\n",solve(x,y));113 ??????}114 ??????if(op[0]==‘R‘){115 ????scanf("%s",d);change(x,d[0]);116 ??????}117 ??????if(op[0]==‘I‘){118 ????scanf("%s",d);insert(x,d[0]);119 ??????}120 ????}121 ??return 0;122 }