Sgu/187

基础的splay

//by hza
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
using namespace std;
 
const int MAX=130000+10;
 
int n,m;
 
int size[MAX],key[MAX],ch[MAX][2],pre[MAX],root;
bool rev[MAX];
 
int swap(int &a,int &b){int t=a;a=b;b=t;}
 
void pushdown(int x)
{
	if(!x)return;
	if(rev[x])
	{
		rev[x]^=1;
		if(ch[x][0])rev[ch[x][0]]^=1;
		if(ch[x][1])rev[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);
	}
}
 
void updata(int x)
{
	if(!x)return;
	pushdown(x);
	pushdown(ch[x][0]);
	pushdown(ch[x][1]);
	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
 
void rorate(int x,int T)
{
	int y=pre[x];
	if(T)
	{
		pre[ch[x][1]]=y;
		ch[y][0]=ch[x][1];
		ch[x][1]=y;
	}else
	{
		pre[ch[x][0]]=y;
		ch[y][1]=ch[x][0];
		ch[x][0]=y;
	}
	pre[x]=pre[y];
	pre[y]=x;
	if(ch[pre[x]][1]==y)ch[pre[x]][1]=x;
	else ch[pre[x]][0]=x;
	updata(x);
	updata(y);
	return;
}
 
void splay(int x,int goal)
{
	if(x==goal)return;
	if(goal==0)root=x;
	int y,t;
	for(;pre[x]!=goal;)
	{
		int y=pre[x],t=pre[y];
		if(t==goal)
			rorate(x,ch[y][0]==x);
		else if(ch[t][0]==y)
		{
			if(ch[y][0]==x){rorate(x,1);rorate(x,1);}
			else if(ch[y][1]==x){rorate(x,0);rorate(x,1);}
		}else
		{
			if(ch[y][1]==x){rorate(x,0);rorate(x,0);}
			else if(ch[y][0]==x){rorate(x,1);rorate(x,0);}
		}
	}
}
 
int rank(int k)
{
	int x=0,done;
	for(;;)
	{
		updata(x);
		if(done+size[ch[x][0]]+1==k)
			return x;
		else if(done+size[ch[x][0]]+1<k)
		{
			done+=size[ch[x][0]]+1;
			x=ch[x][1];
		}else x=ch[x][0];
	}
}
 
void build()
{
	int i,j,k;
	size[0]=0;
	for(i=1;i<=n+2;++i)
	{
		key[i]=i;
		size[i]=n+3-i;
		rev[i]=0;
		if(i+1<=n+2)ch[i][1]=i+1;
		pre[i]=i-1;
	}
	root=1;
}
 
void output()
{
	int i,j,k;
	for(i=2;i<=n+1;++i)
	{
		k=rank(i);
		splay(k,0);
		//cout<<key[k]-1<<" ";
	}
}
void work()
{
	int i,x,y,l,r;
	for(i=1;i<=m;++i)
	{
		cin>>l>>r;
		x=rank(l),y=rank(r+2);
		splay(x,0);
		splay(y,x);
		rev[ch[y][0]]^=1;
	}
	output();
}
 
int main()
{
	freopen("187.in","r",stdin);
	freopen("187.out","w",stdout);
	cin>>n>>m;
	work();
	return 0;
}

/by Logic
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=130050,maxm=2050;
struct Tree
{
	int fa,l,r,key,siz;
	bool re;
}tree[maxn];
int n,m,root=1,now=0;
void get_size(int x)
{
	tree[x].siz=tree[tree[x].l].siz+tree[tree[x].r].siz+1;
}
void build(int fa,int cur,int le,int ri)
{
	tree[cur].fa=fa;
	tree[cur].key=(le+ri)/2;
	tree[cur].re=0;
	if(le>=tree[cur].key) tree[cur].l=0;
	else
	{
		tree[cur].l=now+1;
		build(cur,++now,le,tree[cur].key-1);
	}
	if(ri<=tree[cur].key) tree[cur].r=0;
	else
	{
		tree[cur].r=now+1;
		build(cur,++now,tree[cur].key+1,ri);
	}
	get_size(cur);
}
void update(int x)
{
	if(!x||!tree[x].re) return ;
	tree[x].re=0;
	tree[tree[x].l].re=!tree[tree[x].l].re;
	tree[tree[x].r].re=!tree[tree[x].r].re;
	swap(tree[x].l,tree[x].r);
}
void print(int x)
{
	update(x);
	if(tree[x].l) print(tree[x].l);
	if(tree[x].key&&tree[x].key<=n) printf("%d ",tree[x].key);
	if(tree[x].r) print(tree[x].r);
}
void rot(int x)
{
	int fa=tree[x].fa;
	update(tree[fa].fa);
	update(fa);
	update(x);
	if(tree[fa].l==x)
	{
		tree[fa].l=tree[x].r;
		if(tree[x].r) tree[tree[x].r].fa=fa;
		tree[x].r=fa;
	}
	else
	{
		tree[fa].r=tree[x].l;
		if(tree[x].l) tree[tree[x].l].fa=fa;
		tree[x].l=fa;
	}
	if(root==fa) root=x;
	else if(tree[tree[fa].fa].l==fa) tree[tree[fa].fa].l=x;
	else tree[tree[fa].fa].r=x;
	tree[x].fa=tree[fa].fa;
	tree[fa].fa=x;
	get_size(fa);
	get_size(x);
}
void splay(int x,int c)
{
	int y=tree[x].fa,z=tree[tree[x].fa].fa;
	if((!c&&y==root)||(c&&z==root)) rot(x);
	else if((tree[z].l==y)^(tree[y].l==x)) rot(x),rot(x);
	else rot(y),rot(x);
}
void reverse(int l,int r)
{
	int i;
	update(root);
	for(l++,i=root;l!=tree[tree[i].l].siz+1;)
	{
		if(l<=tree[tree[i].l].siz) i=tree[i].l;
		else l-=tree[tree[i].l].siz+1,i=tree[i].r;
		update(i);
	}
	while(i!=root) splay(i,0);
	for(r++,i=root;r!=tree[tree[i].l].siz+1;)
	{
		if(r<=tree[tree[i].l].siz) i=tree[i].l;
		else r-=tree[tree[i].l].siz+1,i=tree[i].r;
		update(i);
	}
	while(tree[i].fa!=root) splay(i,1);
	tree[tree[i].l].re=!tree[tree[i].l].re;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
#endif
	int i,l,r;
	scanf("%d%d",&n,&m);
	tree[0].siz=0;
	build(0,++now,0,n+1);
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&l,&r);
		reverse(l-1,r+1);
		//print(root),printf("\n");
	}
	print(root);
	return 0;
}