原题传送门
解题思路：裸平衡树操作，支持区间翻转即可，这里写了无旋treap。
其实平衡树的区间操作就和线段树差不多，你用个标记搞一下就好了，，，，，
#include <stdio.h> #define r register #define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),S==TT)?EOF:*S++) char BB[1<<15],*TT=BB,*S=BB; inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar(); while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; } namespace Treap{ inline int Rand(){ static int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5; } struct node{ node *ls,*rs; int val,sz,pri; bool rev; node(int x):val(x),rev(0),sz(1),pri(Rand()){ls=rs=NULL;} void combine(){sz=(ls?ls->sz:0)+(rs?rs->sz:0)+1;} }*root; struct Droot{node *a,*b;}; inline int Size(node *x){return x?x->sz:0;} inline void swap(node *&x,node *&y){r node *t=x;x=y;y=t;} inline node *reverse(node *x){if (!x) return NULL;swap(x->ls,x->rs);x->rev^=1;return x;} inline void pushdown(node *x){if (x->rev) reverse(x->ls),reverse(x->rs),x->rev=0;} node *merge(node*a,node*b){ if (!a) return b;if (!b) return a; if (a->pri<b->pri){ pushdown(a);a->rs=merge(a->rs,b); a->combine();return a; }else{ pushdown(b);b->ls=merge(a,b->ls); b->combine();return b; } } Droot split(node *x,int k){ if (x==NULL) return (Droot){NULL,NULL}; r Droot y;pushdown(x); if (k<=Size(x->ls)){ y=split(x->ls,k);x->ls=y.b; x->combine();y.b=x; }else{ y=split(x->rs,k-Size(x->ls)-1); x->rs=y.a;x->combine();y.a=x; }return y; } inline void Reverse(int L,int R){ r Droot x=split(root,L-1); r Droot y=split(x.b,R-L+1); root=merge(merge(x.a,reverse(y.a)),y.b); } }using namespace Treap; int n,q; void init(){ n=read(),q=read(); for (int i=1; i<=n; ++i) root=merge(root,new node(i)); } void solve(){ while(q--){ r int L=read(),R=read(); Reverse(L,R); }for (r int i=1; i<=n; ++i) { r Droot y=split(root,1); printf("%d ",y.a->val); root=y.b; } } int main(){init(); solve(); return 0;}
转载于:https://www.cnblogs.com/Melacau/p/BZOJ3223.html
