每日归档： 2018年12月16日

虽然说是模板题，但实际上时候在考察Splay一个很巧妙的运用，也就是用Splay模拟区间。
首先我们发现二叉排序树一个很巧妙的性质：对于一个点\(a\)和它的一个孩子\(b\)，若令\(b\)是\(a\)的\(D\)方向的孩子，
那么区间\((a,b)\)内的所有数都在以\(b\)的\(D\ xor\ 1\)方向上的孩子为根的子树中。
然后我们考虑翻转操作。我们毫不惊讶地发现，当我们将一棵子树上的所有节点都左右调换以后，这棵子树所代表的区间就完成了翻转。
对于一个节点来说，它的位置就已经表示了它的大小。
但是，如果对于每一次翻转我们都翻转整棵子树的话，复杂度是不可接受的。我们考虑一种类线段树的操作方法，也就是使用\(Lazy Tag\)来维护翻转。
而，除了翻转操作之外，会改变树的结构的只有旋转操作。于是我们只需要在旋转之前下放\(x\)和\(fa\)的延迟标记即可。
另外尤其要注意不要旋转过头。

#include<iostream>
#include<cstdio>
class Splay{
	private:
		class Node{
			public:
				int v;
				int sz;
				int fa;
				int sn[2];
				int lzy;
		};
		Node tr[200005];
		int rt;
		inline void prnt(int X){
			if(!X){
				return;
			}
			pshd(X);
			prnt(tr[X].sn[0]);
			printf("%d ",tr[X].v);
			prnt(tr[X].sn[1]);
		}
		inline void debugPrnt(int X){
			if(!X){
				return;
			}
			pshd(X);
			debugPrnt(tr[X].sn[0]);
			printf("[%d,%d]{%d}:%d ",tr[X].sn[0],tr[X].sn[1],tr[X].fa,tr[X].v);
			debugPrnt(tr[X].sn[1]);
		}
		inline void pshd(int X){
			if(tr[X].lzy){
				tr[X].lzy^=1;
				tr[tr[X].sn[0]].lzy^=1,tr[tr[X].sn[1]].lzy^=1;
				std::swap(tr[X].sn[0],tr[X].sn[1]);
			}
		}
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
		}
		inline int fndD(int X){
			return tr[tr[X].fa].sn[0]==X?0:1;
		}
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			pshd(tr[X].fa),pshd(X);
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
				splayOne(X);
			}
			rt=X; 
		}
		inline int fnd(int X){
			int P=rt,FP=0;
			while(P){
				pshd(P);
				FP=P;
				if(tr[tr[P].sn[0]].sz+1<X){
					X-=(tr[tr[P].sn[0]].sz+1);
					P=tr[P].sn[1];
				}else if(tr[tr[P].sn[0]].sz<X){
					return P;
				}else{
					P=tr[P].sn[0];
				}
			}
			return FP;
		}
	public:
		inline void build(int N){
			for(int i=1;i<=N;++i){
				tr[i].sn[0]=i-1;
				tr[i].v=i;
				tr[i].fa=i+1;
				tr[i].sz=1;
			}
			tr[N].fa=0;
			tr[1].sn[0]=N+1,tr[N].sn[1]=N+2;
			tr[N+1].v=-2147483647,tr[N+2].v=2147483647;
			tr[N+1].fa=1,tr[N+2].fa=N;
			tr[N+1].sz=1,tr[N+2].sz=1;
			rt=N;
			splayRnw(N+1);
			splayRnw(N+2);
		}
		inline void flp(int L,int R){
			//printf("[%d](%d,%d)\n",rt,fnd(L),fnd(R+2));
			splayRnw(fnd(L));
			splayRnw(fnd(R+2));
			tr[tr[tr[rt].sn[0]].sn[1]].lzy^=1;
		}
		inline void splayPrnt(int N){
			splayRnw(N+1);
			splayRnw(N+2);
			prnt(tr[tr[rt].sn[0]].sn[1]);
			puts("");
		}
		inline void debug(){
			printf("%d ->",rt);
			debugPrnt(rt);
			puts("");
		}
};
int n,q;
Splay T;
void init(){
	int n,q;
	scanf("%d%d",&n,&q);
	int l,r;
	T.build(n);
	for(int i=1;i<=q;++i){
		scanf("%d%d",&l,&r);
		T.flp(l,r);
	}
	T.splayPrnt(n);
}
int main(){
	init();
	return 0;
}