BZOJ 1014, 火星人

2019-11-10 19:31:04

字體：大中小

來源：轉載

供稿：網友

PRoblem

傳送門

Mean

給定一僅有小寫字母組成的字符串，要求支持單字符修改、插入和查詢不同起始位置的最長公共前綴長度。

Analysis

用Splay維護字符串，二分+Hash查詢。反反復復WA了很多次，就因為Hash的操作順序不太對……也算是買了個教訓。

Code

#include<cstdio>#include<cstring>typedef long long ll;const int x=31,L=110005,MOD=1000173169;int o,m,a,b,len,cnt,sz[L],f[L],v[L],son[L][2],p[L],h[L];char c,s[L];void up(int o){ int l=son[o][0],r=son[o][1]; sz[o]=sz[l]+sz[r]+1; h[o]=(h[l]+(ll)v[o]*p[sz[l]]%MOD+(ll)h[r]*p[sz[l]+1]%MOD)%MOD;}void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void read(char &c){while(((c=getchar())<'A' || c>'Z') && (c<'a' || c>'z'));}int build(int l,int r,int fa){ int x=++cnt,mid=l+r>>1; f[x]=fa,v[x]=s[mid]-'a'+1; if(l<mid) son[x][0]=build(l,mid-1,x); if(r>mid) son[x][1]=build(mid+1,r,x); up(x); return x;}int kth(int k){ for(int x=o,tmp;;){ tmp=sz[son[x][0]]+1; if(tmp==k) return x; if(tmp>k) x=son[x][0]; else x=son[x][1],k-=tmp; }}void rotate(int x){ int y=f[x],w=son[y][1]==x; if(son[y][w]=son[x][w^1]) f[son[x][w^1]]=y; if(f[x]=f[y]) son[f[y]][son[f[y]][1]==y]=x; son[x][w^1]=y,f[y]=x; up(y);}void splay(int x,int w){ while(f[x]!=w){ int y=f[x]; if(f[y]!=w){ if((son[f[y]][0]==y)^(son[y][0]==x)) rotate(x); else rotate(y); } rotate(x); } if(!w) o=x; up(x);}int query(int x,int l){ int a=kth(x),b=kth(x+l+1); splay(a,0),splay(b,a); return h[son[b][0]];}int solve(int x,int y){ int l=1,r=cnt-y-1,ans=0; while(l<=r){ int mid=l+r>>1; if(query(x,mid)==query(y,mid)) ans=mid,l=mid+1; else r=mid-1; } return ans;}int main(){ scanf("%s",s+1); len=strlen(s+1); p[0]=1; for(int i=1;i<L;i++) p[i]=(ll)p[i-1]*x%MOD; o=build(0,len+1,0); read(m); while(m--){ read(c),read(a); if(c=='Q'){ read(b); printf("%d/n",a<b?solve(a,b):solve(b,a)); }else if(c=='R'){ a=kth(a+1); splay(a,0); read(c); v[a]=c-'a'+1; up(a); }else{ a=kth(a+1); splay(a,0); read(c); f[++cnt]=a,v[cnt]=c-'a'+1; son[cnt][1]=son[a][1],f[son[a][1]]=cnt,son[a][1]=cnt; up(cnt),up(a); } } return 0;}

上一篇：文章標題

下一篇：MFC 程序入口和執行流程