BZOJ 1014 [JSOI2008]火星人prefix | Splay维护哈希值

#include<cstdio>#include<algorithm>#include<cstring>typedef long long ll;#define N 100010#define Base 29#define which(x) (ls[fa[(x)]]==(x))using namespace std;int n,m,idx,root,fa[N],ls[N],rs[N],val[N],sz[N],a,b;ll hsh[N],pw[N];char s[N],op[10];void upt(int u){ ???sz[u]=sz[ls[u]]+sz[rs[u]]+1; ???hsh[u]=hsh[ls[u]]+val[u]*pw[sz[ls[u]]]+hsh[rs[u]]*pw[sz[ls[u]]+1];}void rotate(int u){ ???int v=fa[u],w=fa[v],b=which(u)?rs[u]:ls[u]; ???if (w) which(v)?ls[w]=u:rs[w]=u; ???which(u)?(ls[v]=b,rs[u]=v):(rs[v]=b,ls[u]=v); ???fa[u]=w,fa[v]=u; ???if (b) fa[b]=v; ???upt(v),upt(u);}void splay(int u,int tar){ ???while (fa[u]!=tar) ???{ ???if (fa[fa[u]]!=tar) ???????(which(u)==which(fa[u]))?rotate(fa[u]):rotate(u); ???rotate(u); ???} ???if (!tar) root=u;}int build(int l,int r,int pre){ ???if (l>r) return 0; ???int u=++idx,mid=l+r>>1; ???val[u]=s[mid]-‘a‘+1,fa[u]=pre; ???ls[u]=build(l,mid-1,u); ???rs[u]=build(mid+1,r,u); ???upt(u); ???return u;}int find(int x){ ???int u=root; ???while(sz[ls[u]]!=x) ???if (x<=sz[ls[u]]-1) u=ls[u]; ???else x-=sz[ls[u]]+1,u=rs[u]; ???return u;}void insert(int pos,int x){ ???int u=find(pos),v=find(pos+1); ???splay(u,0),splay(v,u); ???ls[v]=++idx,fa[idx]=v,val[idx]=x,sz[idx]=1; ???splay(idx,0);}void change(int pos,int x){ ???int u=find(pos); ???val[u]=x; ???splay(u,0);}ll gethsh(int pos,int len){ ???int u=find(pos-1),v=find(pos+len); ???splay(u,0),splay(v,u); ???return hsh[ls[v]];}int query(int a,int b){ ???int l=0,r=sz[root]-max(a,b)-1,mid; ???while (l<r) ???{ ???mid=l+r+1>>1; ???if (gethsh(a,mid)==gethsh(b,mid)) l=mid; ???else r=mid-1; ???} ???return l;}int main(){ ???scanf("%s",s+1); ???n=strlen(s+1); ???pw[0]=1; ???for (int i=1;i<N;i++) ???pw[i]=pw[i-1]*Base; ???root=build(0,n+1,0); ???scanf("%d",&m); ???while (m--) ???{ ???scanf("%s",op); ???if (op[0]==‘Q‘) ???{ ???????scanf("%d%d",&a,&b); ???????printf("%d\n",query(a,b)); ???} ???else if (op[0]==‘I‘) ???{ ???????int pos; ???????scanf("%d%s",&pos,op); ???????insert(pos,op[0]-‘a‘+1); ???} ???else if (op[0]==‘R‘) ???{ ???????int pos; ???????scanf("%d%s",&pos,op); ???????change(pos,op[0]-‘a‘+1); ???} ???} ???return 0;}