记录编号	432260	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.417 s
提交时间	2017-08-03 09:20:27	内存使用	0.70 MiB

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <ctime>
#define maxn 100500
using namespace std;
int n,m,l,r;
struct treap{
	   treap *ch[2];
	   int v,rd,flip,size;
	   treap(){size=flip=v=0;rd=rand();ch[0]=ch[1]=NULL;}
	   void update(){size=ch[0]->size+1+ch[1]->size;}
}*null=new treap(),*root=null,*stack[maxn],*x,*last;
//flip类似于标记，标记要旋转的子树
//stack维护树上的最右端的一条链，序列操作以权值建树，要维持中序遍历不变 
//如果遇到以权值建树的情况，sort一遍之后同理 
typedef pair<treap*,treap*> tree;
treap* newtreap(int v){
	   treap *k=new treap();
	   k->size=1;
	   k->v=v;
	   k->ch[0]=k->ch[1]=null;
	   return k;
}
void pushdown(treap *k){//标记下放 
	 if(k==null) return;
	 if(k->flip){//有标记则旋转子树 
	 	k->flip^=1;
	 	if(k->ch[0]!=null) k->ch[0]->flip^=1;
	 	if(k->ch[1]!=null) k->ch[1]->flip^=1;
	 	swap(k->ch[0],k->ch[1]);
	 }
}
treap* build(){//新点先插放在最右端，如果其父亲小于其rd，pop出其父亲，
//将其左子树置为其父亲，可手推其中序遍历不变，直至满足查找树性质 
	 int p=0;
	 for(int i=1;i<=n;i++){
	 	 x=newtreap(i);
	 	 last=null;
	 	 while(p&&stack[p]->rd > x->rd){
	 	 	   stack[p]->update();
	 	 	   last=stack[p];
	 	 	   stack[p--]=null;
		 }
		 if(p) stack[p]->ch[1]=x;
		 x->ch[0]=last;
		 stack[++p]=x;
	 }
	 while(p) stack[p--]->update();
	 return stack[1]; 
}
treap* merge(treap *a,treap *b){//合并 
	   if(a==null) return b;
	   if(b==null) return a;
	   pushdown(a);
	   pushdown(b);
	   //b接在a后面，注意顺序不可变，中序遍历不变 
	   if(a->rd < b->rd){
	      a->ch[1]=merge(a->ch[1],b);
	      a->update();
	      return a;
	   }
	   else{
	   	  b->ch[0]=merge(a,b->ch[0]);
	   	  b->update();
	   	  return b;
	   }
}
tree split(treap *k,int pre){//k为根 ，删除该子树的前pre个数
     if(k==null) return tree(null,null);
	 pushdown(k);
	 tree y;
	 if(k->ch[0]->size>=pre){
	 	y=split(k->ch[0],pre);
	 	k->ch[0]=y.second;
	 	k->update();
	 	y.second=k;
	 } 
	 else{
	 	y=split(k->ch[1],pre-k->ch[0]->size-1);
	 	k->ch[1]=y.first;
	 	k->update();
	 	y.first=k;
	 }   
	 return y;
}
void change(int le,int ri){
	 tree x=split(root,ri);
	 tree y=split(x.first,le-1);
	 if(y.second!=null) y.second->flip^=1;
	 root=merge(merge(y.first,y.second),x.second);
}
void dfs(treap *k){
	 if(k==null) return;
	 pushdown(k);
	 if(k->ch[0]!=null) dfs(k->ch[0]);
	 printf("%d ",k->v);
	 if(k->ch[1]!=null) dfs(k->ch[1]);
}
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	scanf("%d%d",&n,&m);
	root=build();
	while(m--){
		  scanf("%d%d",&l,&r);
		  change(l,r);
	}
	dfs(root);//中序遍历 
}
/*
5 3
1 3
1 3
1 4
*/