题干：splay模板，要求维护区间反转。
splay是一种码量小于treap，但支持排名，前驱后继等treap可求的东西，也支持区间反转的平衡树。
但是有两个坏处：
1.splay常数远远大于treap以及stl中的set。
2.没有可持久化splay，但有可持久化treap。
下面是代码：
1.pushup以及pushdown
pushup用于维护某点所在子树大小。
void pushup(int u)
{
tr[u].siz = tr[tr[u].ch[]].siz + tr[tr[u].ch[]].siz + ;
}
一行。
pushdown用于标记下推。
void pushdown(int u)
{
if(tr[u].mrk)
{
tr[u].mrk=;
swap(tr[u].ch[],tr[u].ch[]);
tr[tr[u].ch[]].mrk^=;
tr[tr[u].ch[]].mrk^=;
}
}
2.rotate
rotate相当于treap中的lturn和rturn，是将x点转到他的父节点处。
void rotate(int x)
{
int y = tr[x].fa;
int z = tr[y].fa;
int k = (tr[y].ch[]==x);
tr[x].fa = z,tr[z].ch[tr[z].ch[]==y]=x;
tr[y].ch[k] = tr[x].ch[k^],tr[tr[x].ch[k^]].fa = y;
tr[y].fa = x,tr[x].ch[k^]=y;
pushup(y),pushup(x);
}
注意改变父子关系时的顺序问题，还有两个pushup，应该先pushup儿子后pushup父亲。
3.splay（splay核心操作）
splay（a，b），将a旋转到b的儿子处。
下面是双旋splay：
void splay(int x,int goal)
{
while(tr[x].fa!=goal)
{
int y = tr[x].fa;
int z = tr[y].fa;
if(z!=goal)
((tr[z].ch[]==y)^(tr[y].ch[]==x))?rotate(x):rotate(y);
rotate(x);
}
if(goal==)rot=x;
}
代码中while中的if，机房普遍认为是为了维护整棵树的深度。
4.insert
码量比treap少很多：
void insert(int x)
{
int u = rot,fa;
while(u)fa=u,u=tr[u].ch[tr[u].v<x];
u=++tot;
if(fa)tr[fa].ch[x>tr[fa].v]=u;
tr[u].fa = fa,tr[u].v = x,tr[u].siz = ;
splay(u,);
}
5.查询排名
代码：
int query_kth(int k)
{
int u = rot;
while()
{
pushdown(u);
int t = tr[tr[u].ch[]].siz;
if(t==k-)return u;
else if(t>=k)u=tr[u].ch[];
else k-=t+,u=tr[u].ch[];
}
}
6.区间旋转
先查询前驱后继，然后把所在子树夹到前驱后继之间，一个标记解决问题。
void chg(int l,int r)
{
l = query_kth(l);//前驱
r = query_kth(r+);//后继
splay(l,);splay(r,l);
tr[tr[tr[rot].ch[]].ch[]].mrk^=;
}
最后：
推极大极小,推极大极小，推极大极小！！！
全代码就不粘了。