Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 4521 Solved: 2633 [Submit][Status][Discuss] 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这里写代码片
Source
平衡树 不想动脑子
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; int n,m,cnt,fa[MAXN],tr[MAXN][2],v[MAXN],sz[MAXN],rt; bool rev[MAXN]; void pushup(int x){ int l=tr[x][0],r=tr[x][1]; sz[x]=sz[l]+sz[r]+1; } void pushdown(int x){ if(rev[x]){ swap(tr[x][0],tr[x][1]); rev[x]=0;rev[tr[x][0]]^=1;rev[tr[x][1]]^=1; } } int find(int x,int rk){ pushdown(x); int l=tr[x][0],r=tr[x][1]; if(sz[l]+1==rk)return x; else if(rk<=sz[l])return find(l,rk); else return find(r,rk-sz[l]-1); } void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(tr[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else{if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;} fa[x]=z;fa[y]=x;fa[tr[x][r]]=y; tr[y][l]=tr[x][r];tr[x][r]=y; pushup(y);pushup(x); } void splay(int x,int &k){ int y,z; while(x!=k){ y=fa[x],z=fa[y]; if(y!=k){ if((tr[y][0]==x) ^ (tr[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int &k,int l,int r,int pr){ if(k==0){k=++cnt;fa[k]=pr;} int mid = l+r>>1; v[k]=mid; sz[k]=1; if(l==r)return; if(l<=mid-1) build(tr[k][0],l,mid-1,k); if(mid+1<=r) build(tr[k][1],mid+1,r,k); pushup(k); } void rever(int l,int r){ int x = find(rt,l); int y = find(rt,r+2); splay(x,rt); splay(y,tr[rt][1]); int z = tr[y][0]; rev[z]^=1; } void dfs(int k){ if(k==0)return; pushdown(k); dfs(tr[k][0]); printf("%d ",v[k]); dfs(tr[k][1]); } int main(){ scanf("%d %d",&n,&m); build(rt,0,n+5,0); // dfs(rt); for(int i=1;i<=m;i++){ int l,r; scanf("%d %d",&l,&r); // l++;r++; rever(l,r); } for(int i=1;i<=n;i++){ printf("%d ",v[find(rt,i+1)]); } return 0; }