记录编号	432702	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	1.306 s
提交时间	2017-08-03 17:56:01	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,num,x,y;
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
struct Splay{
	int num,size;bool tag;
	Splay *fa,*ch[2];
	void pushup(){
		size=ch[0]->size+ch[1]->size+1;
	}
	bool get(){
		return fa->ch[0]==this?0:1;
	}
	void set(Splay*,int);
}pool[N],*null,*root; 
void Splay::set(Splay *child,int wh){
	ch[wh]=child;
	if(child!=null) child->fa=this;
	pushup();
	return;
}
Splay* newnode(int x){
	Splay *t=&pool[++num];
	t->ch[0]=t->ch[1]=null;
	t->num=x;t->size=1;t->tag=false;
	return t;
}
Splay* build(int l,int r,Splay *now){
	if(l>r) return null;
	int mid=(l+r)>>1;
	Splay *t=newnode(mid);
	t->fa=now;
	t->ch[0]=build(l,mid-1,t);
	t->ch[1]=build(mid+1,r,t);
	t->pushup();
	return t;
}
void pushdown(Splay *now){
	if(now->tag){
		swap(now->ch[0],now->ch[1]);
		if(now->ch[0]!=null) now->ch[0]->tag^=1;
		if(now->ch[1]!=null) now->ch[1]->tag^=1;
		now->tag^=1;
	}
}
Splay *kth(int k){
	Splay *now=root;
	while(now!=null){
		pushdown(now);
		if(now->ch[0]->size+1==k) return now;
		if(now->ch[0]->size+1>k) now=now->ch[0];
		else k-=now->ch[0]->size+1,now=now->ch[1];
	}
	return null;	
}
Splay *find(int v){
	Splay *now=root;
	int left=0;
	while(now!=null){
		pushdown(now);
		int tt=left+now->ch[0]->size;
		if(v==tt+1) return now;
		if(tt+1>v) now=now->ch[0];
		else left=tt+1,now=now->ch[1];
	}
}
void rotate(Splay *&now){
	Splay *pa=now->fa;
	Splay *ga=pa->fa;
	if(ga->tag) pushdown(ga);
	if(pa->tag) pushdown(pa);
	if(now->tag) pushdown(now);
	int wz=now->get();
	pa->set(now->ch[wz^1],wz);now->set(pa,wz^1);
	now->fa=ga;
	if(ga!=null) ga->ch[ga->ch[1]==pa]=now;
}
void splay(Splay *now,Splay *lim){
	for(;now->fa!=lim;rotate(now))
		if(now->fa->fa!=lim)
			now->get()==now->fa->get()?rotate(now->fa):rotate(now);
	if(lim==null) root=now;
}
void Swap(int x,int y){
	Splay *t=kth(x);
	splay(t,null);
	t=kth(y+2);
	splay(t,root);
	root->ch[1]->ch[0]->tag^=1;
}
void search(Splay *now){
	if(!now) return;
	pushdown(now);
	search(now->ch[0]);
	if(now!=null&&now->num&&now->num!=n+1)
		printf("%d ",now->num);
	search(now->ch[1]);
}
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	n=read();m=read();
	null=newnode(-1);
	null->size=0;
	root=newnode((n+1)/2);
	root->fa=null;int mid=(n+1)>>1;
	root->ch[0]=build(0,mid-1,root);
	root->ch[1]=build(mid+1,n+1,root);
	root->pushup();
	for(int i=1;i<=m;++i){
		x=read();y=read();
		Swap(x,y);
	}
	search(root);
	return 0;
}