此为平衡树系列第二道:文艺平衡树您需要写一种数据结构,来维护一个有序数列,其中需要提供以下操作:
翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1
输入
第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出
输出一行n个数字,表示原始序列经过m次变换后的结果
样例输入
5 3
1 3
1 3
1 4
样例输出
4 3 2 1 5
提示
n,m<=100000
非旋转treap相比于旋转treap支持区间操作,所以对于这道题只需要每次把树拆成[1~l-1]、[l~r]、[r+1~tot]三段,然后把[l~r]打上标记进行翻转,再把三段区间合并就行了。对于打标记的点只有在查到这个点时才翻转,如果一个点被打了两次标记就相当于不翻转。
最后附上代码.
指针版
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; char *p1,*p2,buf[100000]; #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) int rd() {int x=0,f=1; char c=nc(); while(!isdigit(c)) {if(c=='-') f=-1; c=nc();} while(isdigit(c)) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;} ll rd2() {ll x=0,f=1; char c=nc(); while(!isdigit(c)) {if(c=='-') f=-1; c=nc();} while(isdigit(c)) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;} int n,m; int L,R; struct treap { int size; int rnd; int val; int rev; treap *ls,*rs; treap(){} treap(int k,treap *son) { size=1; rnd=rand(); val=k; ls=rs=son; rev=0; } void pushup() { size=ls->size+rs->size+1; } void pushdown() { if(rev) { rev^=1; ls->rev^=1; rs->rev^=1; swap(ls,rs); } } }tr[100010],nil; typedef treap* node; node root,cnt,null; void init() { nil=treap(0,NULL); null=&nil; null->ls=null->rs=null; null->size=0; root=null; cnt=tr; } node build(int x) { *cnt=treap(x,null); return cnt++; } node merge(node x,node y) { if(x==null) { return y; } if(y==null) { return x; } x->pushdown(); y->pushdown(); if(x->rnd<y->rnd) { x->rs=merge(x->rs,y); x->pushup(); return x; } else { y->ls=merge(x,y->ls); y->pushup(); return y; } } void split(node rt,node &x,node &y,int k) { if(rt==null) { x=y=null; return ; } rt->pushdown(); if(rt->ls->size>=k) { y=rt; split(rt->ls,x,y->ls,k); rt->pushup(); } else { x=rt; split(rt->rs,x->rs,y,k-rt->ls->size-1); rt->pushup(); } } void print(node rt) { rt->pushdown(); if(rt->ls!=null) { print(rt->ls); } printf("%d",rt->val); if(--n!=0) { printf(" "); } if(rt->rs!=null) { print(rt->rs); } } node build_tree(int l,int r) { if(l==r) { return build(l); } int mid=(l+r)>>1; return merge(build_tree(l,mid),build_tree(mid+1,r)); } int main() { init(); n=rd(); m=rd(); root=build_tree(1,n); while(m--) { L=rd(); R=rd(); node x,y,z; split(root,y,z,R); split(y,x,y,L-1); y->rev^=1; root=merge(merge(x,y),z); } print(root); }
非指针版
#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #include<cstring> using namespace std; int n,m; int r[100010]; int v[100010]; int s[100010][3]; int size[100010]; bool d[100010]; int root; int tot; int L,R; int x,y,z; int flag; void pushup(int x) { size[x]=size[s[x][0]]+size[s[x][1]]+1; } int build(int x) { v[++tot]=x; r[tot]=rand(); size[tot]=1; return tot; } void pushdown(int x) { swap(s[x][0],s[x][1]); if(s[x][0]) { d[s[x][0]]^=1; } if(s[x][1]) { d[s[x][1]]^=1; } d[x]=0; } int merge(int x,int y) { if(!x||!y) { return x+y; } if(r[x]<r[y]) { if(d[x]) { pushdown(x); } s[x][1]=merge(s[x][1],y); pushup(x); return x; } else { if(d[y]) { pushdown(y); } s[y][0]=merge(x,s[y][0]); pushup(y); return y; } } void split(int i,int k,int &x,int &y) { if(!i) { x=y=0; return ; } if(d[i]) { pushdown(i); } if(size[s[i][0]]<k) { x=i; split(s[i][1],k-size[s[i][0]]-1,s[i][1],y); } else { y=i; split(s[i][0],k,x,s[i][0]); } pushup(i); } void print(int x) { if(!x) { return ; } if(d[x]) { pushdown(x); } print(s[x][0]); if(flag==0) { printf("%d",v[x]); flag=1; } else { printf(" %d",v[x]); } print(s[x][1]); } int main() { srand(12378); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { root=merge(root,build(i)); } for(int i=1;i<=m;i++) { scanf("%d%d",&L,&R); split(root,L-1,x,y); split(y,R-L+1,y,z); d[y]^=1; root=merge(merge(x,y),z); } print(root); return 0; }