记录编号	425757	评测结果	AAAAAAAAAA
题目名称	2457.[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	0.960 s
提交时间	2017-07-15 20:00:57	内存使用	1.93 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,x,y;
struct Splay{
	int l[N],r[N],k[N],s[N],root;
	bool tag[N];
	int build(int L,int R){
		if(L>R) return 0;
		int mid=(L+R)>>1;
		s[mid]=R-L+1;
		l[mid]=build(L,mid-1);
		r[mid]=build(mid+1,R);
		return mid;
	}
	void pushdown(int x){
		if(tag[x]){
			swap(l[x],r[x]);
			tag[l[x]]^=1;tag[r[x]]^=1;
			tag[x]^=1;
		}
	}
	void update(int x){
		s[x]=s[l[x]]+s[r[x]]+1;
	}
	void l_rot(int &x){
		int y=r[x];
		r[x]=l[y];l[y]=x;
		update(x);update(y);
		x=y;
	}
	void r_rot(int &x){
		int y=l[x];
		l[x]=r[y];r[y]=x;
		update(x);update(y);
		x=y;
	}
	void splay(int &x,int k){
		pushdown(x);
		int i=s[l[x]]+1;
		if(k==i) return;
		if(k<i) splay(l[x],k),r_rot(x);
		else splay(r[x],k-i),l_rot(x); 
		
	}
	void Swap(int L,int R){
		splay(root,L);
		splay(root,R+2);
		tag[r[l[root]]]^=1;
	}
	void search(int x){
		if(!x) return;
		pushdown(x);
		search(l[x]);
		if(k[x]) printf("%d ",k[x]);
		search(r[x]);
	}
}T;
inline int read(){
	int sum=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum;	
}
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;++i)
		T.k[i+1]=i;
	T.root=T.build(1,n+2);
	for(int i=1;i<=m;++i){
		x=read();y=read();
		T.Swap(x,y);
	}
	T.search(T.root);
	// while(1);
	return 0;
}