记录编号	490094	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][Tyvj 1729] 文艺平衡树	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	2.966 s
提交时间	2018-03-07 12:00:16	内存使用	3.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
using namespace std;
const int maxn=100010;
int n,m,cnt,root,a[maxn],f[maxn],v[maxn],siz[maxn],rev[maxn],ch[maxn][3];
bool Get(int x){return rc(f[x])==x;}
int Isroot(int x){
	return lc(f[x])!=x&&rc(f[x])!=x;
}
void Up(int x){
	if(!x)return;
	siz[x]=1;
	if(lc(x))siz[x]+=siz[lc(x)];
	if(rc(x))siz[x]+=siz[rc(x)];
}
void Down(int x){
	if(!rev[x])return;
	swap(lc(x),rc(x));
	rev[lc(x)]^=1,rev[rc(x)]^=1;
	rev[x]=0;
}
void Rotate(int x){
	Down(f[x]),Down(x);
	int fa=f[x],gf=f[fa],op=Get(x),u=ch[x][op^1];
	if(!Isroot(fa))ch[gf][rc(gf)==fa]=x;
	ch[fa][op]=u,f[u]=fa;
	ch[x][op^1]=fa,f[fa]=x,f[x]=gf;
	Up(fa),Up(x);
}
void Push(int x){
	if(!Isroot(x))Push(f[x]);
	Down(x);
}
void Splay(int x,int y){
	Down(x);
	while(f[x]!=y){
		if(f[f[x]]!=y){
			if(Get(f[x])==Get(x))Rotate(f[x]);
			else Rotate(x);
		}
		Rotate(x);
	}
	if(!y)root=x;
}
int Findkth(int x){
	int now=root;
	while(1){
		Down(now);
		if(siz[lc(now)]>=x)now=lc(now);
		else{
			int tmp=1;
			if(lc(now))tmp=siz[lc(now)]+1;
			if(tmp>=x)return now;
			x-=tmp,now=rc(now);
		}
	}
}
int Build(int l,int r,int fa){
	if(l>r)return 0;
	int mid=(l+r)>>1,now=++cnt;
	ch[now][0]=Build(l,mid-1,now);
	ch[now][1]=Build(mid+1,r,now);
	f[now]=fa,rev[now]=0,v[now]=a[mid];
	Up(now);
	return now;
}
void Print(int x){
	Down(x);
	if(lc(x))Print(lc(x));
	if(v[x]!=inf&&v[x]!=-inf)printf("%d ",v[x]);
	if(rc(x))Print(rc(x));
}
int main(){
	freopen("sph.in","r",stdin);
	freopen("sph.out","w",stdout);
	scanf("%d%d",&n,&m);
	a[0]=-inf,a[n+1]=inf;
	for(int i=1;i<=n;i++)a[i]=i;
	root=Build(0,n+1,0);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		int xx=Findkth(x),yy=Findkth(y+2);
		Splay(xx,0),Splay(yy,xx);
		rev[lc(rc(root))]^=1;
	}
	Print(root);
	return 0;
}