BZOJ 3223, 文藝平衡樹

2019-11-11 04:21:08

字體：大中小

來源：轉載

供稿：網友

PRoblem

傳送門

Mean

編寫一個支持對數列進行翻轉子串操作的數據結構。

Analysis

Splay裸題。只需要支持翻轉操作即可。輸出數列時一個一個查詢就是了……

Code

#include<cstdio>const int N=100005;int n,m,o,x,y,cnt,a[N],val[N],f[N],sz[N],son[N][2];bool rev[N];void swap(int &x,int &y){int z=x;x=y;y=z;}void revl(int x){if(!x) return;swap(son[x][0],son[x][1]);rev[x]^=1;}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 pb(int x){ if(rev[x]){ revl(son[x][0]); revl(son[x][1]); rev[x]=0; }}void up(int x){ int l=son[x][0],r=son[x][1]; sz[x]=sz[l]+sz[r]+1;}int build(int l,int r,int fa){ int x=++cnt,mid=l+r>>1; f[x]=fa,val[x]=mid; 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){ int x=o,tmp; while(1){ pb(x); tmp=sz[son[x][0]]+1; if(tmp==k) return x; if(tmp>k) x=son[x][0]; else k-=tmp,x=son[x][1]; }}void rotate(int x){ int y=f[x],w=son[y][1]==x; son[y][w]=son[x][w^1]; if(son[x][w^1]) f[son[x][w^1]]=y; if(f[y]) son[f[y]][son[f[y]][1]==y]=x; f[x]=f[y],son[x][w^1]=y,f[y]=x; up(y);}void splay(int x,int w){ int s=1,i=x,y;a[1]=x; while(f[i]) a[++s]=i=f[i]; while(s) pb(a[s--]); while(f[x]!=w){ 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 main(){ read(n),read(m); o=build(0,n+1,0); while(m--){ read(x),read(y); x=kth(x),y=kth(y+2); splay(x,0),splay(y,x); revl(son[y][0]); up(y),up(x); } for(int i=2;i<=n;i++) printf("%d ",val[kth(i)]); printf("%d",val[kth(n+1)]); return 0;}

上一篇：JVM之整體架構

下一篇：夕拾算法進階篇：15)最長公共子序列(動態規劃DP)