学完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<r){build(e[u].ch[0],l,mid,u);build(e[u].ch[1],mid+1,r,u);e[u].siz+=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz;}
}
就用递归从中间建起
区间操作
我们想要从树中找到我们需要的区间,怎么办呢?
这个时候就是发挥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<iostream>
#include<cstdio>
#include<algorithm>
#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<r){build(e[u].ch[0],l,mid,u);build(e[u].ch[1],mid+1,r,u);e[u].siz+=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz;}
}void print(int u)
{if(u){if(lazy[u]) pd(u);print(e[u].ch[0]);if(e[u].v>=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<<endl;*/}print(root);cout<<endl;//system("pause >nul");return 0;
}