3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 5644 Solved: 3362[][][]Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3 1 3 1 3 1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
裸的区间翻转
具体操作： 旋转[l,r] 把l-1调到根,r+1调到根右儿子,那么r+1左子树就是[l,r]区间,对这颗子树的根加一个rev标记即可
查询的时候,如果当前节点被rev标记,应该交换左右儿子去寻找,并向下传标记
#include#include #include #include #define N 100050using namespace std;int n,m,rt,id[N],fa[N],ch[N][2],rev[N],siz[N];void pushup(int u){ int l=ch[u][0],r=ch[u][1]; siz[u]=siz[l]+siz[r]+1; }void pushdown(int u){ if(!rev[u])return; int l=ch[u][0],r=ch[u][1]; swap(ch[u][0],ch[u][1]); rev[l]^=1;rev[r]^=1; rev[u]=0; }void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; l= ch[y][1]==x;r=l^1; if(y==k)k=x; else ch[z][ch[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[ch[x][r]]=y; ch[y][l]=ch[x][r];ch[x][r]=y; pushup(y);pushup(x); }void splay(int x,int &k){ while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); }}void build(int l,int r,int f){ if(l>r)return; int now=id[l],ls=id[f]; if(l==r){ fa[now]=ls;siz[now]=1; ch[ls][l>f]=now;return; } int mid=(l+r)>>1;now=id[mid]; build(l,mid-1,now);build(mid+1,r,now); fa[now]=ls;pushup(now); ch[ls][now>ls]=now;}int find(int u,int rk){ pushdown(u); int l=ch[u][0],r=ch[u][1]; if(siz[l]+1==rk)return u; else if(siz[l]>=rk)return find(l,rk); return find(r,rk-siz[l]-1); }void rever(int l,int r){ int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,ch[x][1]); rev[ch[y][0]]^=1;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n+2;i++)id[i]=i; build(1,n+2,0);rt=(n+3)>>1; int l,r; while(m--){ scanf("%d%d",&l,&r); rever(l,r); } for(int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1); return 0;}