BZOJ 1014 ?[JSOI2008]火星人prefix

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<ctime>#define lc ch[x][0]#define rc ch[x][1]typedef unsigned long long LL;const int maxn=300000+299;using namespace std;int len,root,tot,T,x,y,sz[maxn],ch[maxn][2],p[maxn];LL v[maxn],ha[maxn],base=131,power[maxn];char s[maxn],op[10],c[10];inline int read() { ???char ch=getchar(); int f=1,ret=0; ???while(ch!=‘-‘&&(ch>‘9‘||ch<‘0‘)) ch=getchar(); ???if(ch==‘-‘) f=-1,ch=getchar(); ???for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) ret=ret*10+ch-‘0‘; ???return ret*f;}void update(int x) { ???sz[x]=sz[lc]+sz[rc]+1; ???ha[x]=(ha[lc]*power[sz[rc]+1]+v[x]*(power[sz[rc]])+ha[rc]);}void rotate(int x) { ???int y=p[x],z=p[y],l=(x==ch[y][1]),r=l^1; ???if(z) ch[z][y==ch[z][1]]=x; p[x]=z; ???ch[y][l]=ch[x][r]; p[ch[x][r]]=y; ???ch[x][r]=y; p[y]=x; ???update(y); update(x);}void splay(int x,int FA) { ???if(p[x]==FA) return; ???for(;p[x]!=FA;rotate(x)) { ???????int y=p[x],z=p[y]; ???????if(z!=FA) (y==ch[z][1])^(x==ch[y][1])?rotate(x):rotate(y); ???} ???if(!FA) root=x;}int build(int l,int r) { ???int x=++tot; ???sz[x]==1; ???int mid=(l+r)>>1; ???v[x]=s[mid-1]; ???if(mid-1>=l) lc=build(l,mid-1); ???if(mid+1<=r) rc=build(mid+1,r); ???if(lc) p[lc]=x; ???if(rc) p[rc]=x; ???update(x); ???return x;}int kth(int k) { ???int res=-1; ???for(int x=root;x;) { ???????if(sz[lc]+1==k) return x; ???????if(sz[lc]+1>k) x=lc; ???????else k-=(sz[lc]+1),x=rc; ???}}LL find(int l,int r) { ???int ll=kth(l),rr=kth(r); ???if(ll==rr) return v[ll]; ???splay(ll,0); ???splay(rr,ll); ???LL res=v[root]*power[sz[ch[ch[root][1]][0]]+1]+ha[ch[ch[root][1]][0]]*power[1]+v[ch[root][1]]; ???return res;}int ef(int x,int y) { ???int res=0; ???if(x>y) swap(x,y); ???if(x==y) return sz[root]-y+1; ???int l=0,r=sz[root]-y; ???while(l<=r) { ???????int mid=(l+r)>>1; ???????if(find(x,x+mid)==find(y,y+mid)) res=mid+1,l=mid+1; ???????else r=mid-1; ???} ???return res;}int main(){ ???scanf("%s",s); ???len=strlen(s); ????power[0]=1; ???for(int i=1;i<=maxn-290;i++) power[i]=power[i-1]*base; ???root=build(1,len); ???T=read(); ???while(T--) { ???????scanf("%s",op); ???????if(op[0]==‘Q‘) { ???????????scanf("%d%d",&x,&y); ???????????printf("%d\n",ef(x,y)); ???????} ???????else if(op[0]==‘R‘) { ???????????scanf("%d%s",&x,c); ???????????int ll=kth(x); ???????????splay(ll,0); ???????????v[root]=c[0]; ???????????update(root); ???????} ???????else { ???????????scanf("%d%s",&x,c); ???????????if(x==0) { ???????????????int ll=kth(1); ???????????????splay(ll,0); ???????????????ch[root][0]=++tot; ???????????????sz[tot]=1; p[tot]=root; ???????????????v[tot]=ha[tot]=c[0]; ???????????????update(root); ???????????} ???????????else { ???????????????int ll=kth(x); ???????????????splay(ll,0); ???????????????if(x==sz[root]) { ???????????????????ch[root][1]=++tot; ???????????????????sz[tot]=1; p[tot]=root; ???????????????????v[tot]=ha[tot]=c[0]; ???????????????????update(root); ???????????????} ???????????????else { ???????????????????int ll=kth(x); ???????????????????splay(ll,0); ???????????????????int rr=kth(x+1); ???????????????????splay(rr,ll); ???????????????????ch[rr][0]=++tot; ???????????????????sz[tot]=1; p[tot]=rr; ???????????????????v[tot]=ha[tot]=c[0]; ???????????????????update(rr); ???????????????????update(root); ???????????????} ???????????} ???????} ???} ???return 0;}