学完Splay的查找作用，发现和普通的二叉查找树没什么区别，只是用了splay操作节省了时间开支。

而Splay序列之王的称号可不是白给的。

Splay真正强大的地方是他的区间操作。

怎么实现呢？

我们知道查找树的中序遍历是一个有序的序列。这个时候我们打破查找树左小右大的规则，而是把他的中序遍历作为我们的区间进行维护。

具体来讲有以下操作：

1、建树

2、区间操作【翻转、赋值啊什么的】

3、输出序列

建树

既然是区间，我们可以借鉴线段树的建树

void build(int& u,int l,int r,int fa){	if(l>=r) return;	u=++siz;	int mid=(l+r)>>1;	e[u].v=mid;	e[u].siz=1;	e[u].f=fa;	if(l+1

就用递归从中间建起

区间操作

我们想要从树中找到我们需要的区间,怎么办呢?

这个时候就是发挥Splay威力的时候了> <

Splay的伸展操作【也就是splay操作】可以在不改变中序遍历的前提下改变树的结构，也就是说我们可以在不改变序列的前提下改变树的形态。

那么这个时候，如果我们要操作区间[l,r]我们只需将l-1翻转到根节点，将r+1翻转到根节点的右儿子

这个时候想想，r+1的左子树是什么？

没错！就是我们要的区间[l,r]

怎么找到这两个节点？

就套用splay中的查找第k大节点就好了【其实在这里不能说是第k大，是第k个】

但是我们如果要操作[1,N]怎么办？

我们加一个0和N+1节点不就好啦【哨兵】

至于找到区间后怎么操作，就因题而异啦，一般都会加上一个lazy标记节省时间

附上splay操作

#define isr(x) (e[e[x].f].ch[1]==x)...........inline void spin(int u){	int fa=e[u].f,s=isr(u);	e[u].f=e[fa].f;	if(e[fa].f)      e[e[fa].f].ch[isr(fa)]=u;	e[fa].ch[s]=e[u].ch[s^1];	e[fa].f=u;	if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;	e[u].ch[s^1]=fa;	up(fa);up(u);}void splay(int u,int fa=0){	while(e[u].f!=fa)	{		if(e[e[u].f].f&&lazy[e[e[u].f].f]) pd(e[e[u].f].f);		if(lazy[e[u].f])            pd(e[u].f);		if(lazy[u])                 pd(u);		if(e[e[u].f].f==fa)         spin(u);		else if(isr(u)^isr(e[u].f)) spin(u),spin(u);		else                        spin(e[u].f),spin(u);	}	if(!fa) root=u;}

其中lazy是打的标记，splay的时候记得下传【凡是涉及到儿子的操作都要考虑标记下传】

pd是标记下传函数

输出序列

其实就是中序遍历嘛，自己打【其实是我懒】

来道裸题：

洛谷P3391 文艺平衡树

裸的区间翻转

#include
     
      #include
      
       #include
       
        #define isr(x) (e[e[x].f].ch[1]==x)using namespace std;const int maxn=200005,INF=2000000000;int N,M;inline int read(){	int out=0,flag=1;char c=getchar();	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}	while(c>=48&&c<=57){out=out*10+c-48;c=getchar();}		return out*flag;}int lazy[maxn];class node{	public:		int v,ch[2],f,siz;		node() {ch[0]=ch[1]=0;siz=0;}}e[maxn];int siz=0,root=0;inline void up(int u){e[u].siz=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz+1;}inline void pd(int u){	swap(e[u].ch[0],e[u].ch[1]);	lazy[e[u].ch[0]]^=1;	lazy[e[u].ch[1]]^=1;	lazy[u]^=1;}inline void spin(int u){	int fa=e[u].f,s=isr(u);	e[u].f=e[fa].f;	if(e[fa].f)      e[e[fa].f].ch[isr(fa)]=u;	e[fa].ch[s]=e[u].ch[s^1];	e[fa].f=u;	if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;	e[u].ch[s^1]=fa;	up(fa);up(u);}void splay(int u,int fa=0){	while(e[u].f!=fa)	{		if(e[e[u].f].f&&lazy[e[e[u].f].f]) pd(e[e[u].f].f);		if(lazy[e[u].f])            pd(e[u].f);		if(lazy[u])                 pd(u);		if(e[e[u].f].f==fa)         spin(u);		else if(isr(u)^isr(e[u].f)) spin(u),spin(u);		else                        spin(e[u].f),spin(u);	}	if(!fa) root=u;}/*void insert(int& u,int v,int fa){	if(!u) {e[u=++siz].v=v;e[u].f=fa;splay(u);}	else if(e[u].v>v) insert(e[u].ch[0],v,u);	else insert(e[u].ch[1],v,u);}*/int kth(int u,int k){	if(lazy[u]) pd(u);	if(k==e[e[u].ch[0]].siz+1) {/*splay(u);*/return u;}	else if(k>e[e[u].ch[0]].siz+1) return kth(e[u].ch[1],k-e[e[u].ch[0]].siz-1);	return kth(e[u].ch[0],k);	}void change(int l,int r){	int L=kth(root,l),R=kth(root,r+2);	splay(L);	splay(R,root);	lazy[e[e[root].ch[1]].ch[0]]^=1;}void build(int& u,int l,int r,int fa){	if(l>=r) return;	u=++siz;	int mid=(l+r)>>1;	e[u].v=mid;	e[u].siz=1;	e[u].f=fa;	if(l+1
        
         =1&&e[u].v<=N) printf("%d ",e[u].v);		print(e[u].ch[1]);	}}int main(){	N=read();	M=read();	int a,b;	build(root,0,N+2,0);	while(M--)	{		a=read();		b=read();		if(a==b) continue;		change(a,b);		/*print(root);		cout<
         
          nul");	return 0;}