记录编号	312743	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.930 s
提交时间	2016-09-27 14:37:59	内存使用	1.91 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
struct Splay{
	int l[N],r[N],k[N],s[N],root;bool tag[N];
	void update(int x){
		s[x]=s[l[x]]+s[r[x]]+1;
	}
	void pushdown(int x){
		if (tag[x]){
			swap(l[x],r[x]);
			tag[l[x]]^=1;tag[r[x]]^=1;
			tag[x]=0;
		}
	}
	void l_rotate(int &x){
		int y=r[x];
		r[x]=l[y];l[y]=x;
		update(x);update(y);
		x=y;
	}
	void r_rotate(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_rotate(x);
			else splay(r[x],k-i),l_rotate(x);
	}
	int build(int L,int R){
		if (L>R) return 0;
		int mid=(L+R)/2;
		s[mid]=R-L+1;
		l[mid]=build(L,mid-1);
		r[mid]=build(mid+1,R);
		return mid;
	}
	void Swap(int L,int R){
		splay(root,L);
		splay(root,R+2);
		tag[r[l[root]]]^=1;
	}
	void bianli(int x){
		if (!x) return;
		pushdown(x);
		bianli(l[x]);
		if (k[x]) printf("%d ",k[x]);
		bianli(r[x]);
	}
}T;
int n,m;
int main()
{
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) T.k[i+1]=i;
	T.root=T.build(1,n+2);
	while (m--){
		int l,r;
		scanf("%d%d",&l,&r);
		T.Swap(l,r);
	}
	T.bianli(T.root);puts("");
	return 0;
}