写在前面： 部分来自孙宝（@Steven24）的博客，表示感谢。
认识
什么是Splay
就是BST的一种，整体效率是很高的，均摊的次数是O(logn)级别的。
基本操作就是把节点旋转到BST的root，从而改善BST的平衡性，但是很多人会在旋转中转晕
建议找个动图看看，或是上B站找个几分钟的视频看看就理解了。
烧烤
如何可以把一个节点旋转到BST的root的地方，这是Splay的核心，为了完成这个操作，我们主要是需要分成两步：
1.每旋转一次，就使得我们的目标节点x的层次上升一层，最后到达root层
2.在旋转完后，BST的平衡性被破坏了，这是毋庸置疑的，所以我们需要进行一系列的调整，使这棵BST重新回到平衡状态
显然，如果只考虑1，那么使用Treap树的旋转法即可，每次x与x的父亲交换位置（x上升一层）。可Treap树的这种“单旋”并不能减少BST的层数。
所以我们就升级一下，再拉来一个更能打的，祖父节点，让这三代人一起转。
Splay旋转
#define left 0,right 1
这个就是LL,RR,LR,RL四个Splay的基本模型
网上有很多
自己看吧
我推荐这个，因为我就是看着他弄懂的基础知识
Splay四种模型
Splay操作
由于支持单点旋转改变平衡因子的特性Splay常用于处理区间分裂和合并问题。
例如：一个常见的区间操作，修改或查询区间[L,R]，用Splay树就很容易实现：先把L-1旋转到根，然后把节点R+1旋转到L-1的右子树上，此时，L+1的左子树就是区间[L,R]。
1.旋转：
rotate(x)对x点进行一次旋转，若x是一个右儿子，左旋，反之亦反之。
Splay Rotate
void rotate(int x)//单旋一次
{
int f=t[x].fa;//f：父亲
int g=t[f].fa;//g：祖父
int son=get(x);
if(son==1)//x是左儿子，右旋
{
t[f].rs=t[x].ls;
if(t[f].rs)
{
t[t[f].rs].fa=f;
}
}
else//x是右儿子，左旋
{
t[f].ls=t[x].rs;
if(t[f].ls)
{
t[t[f].ls].fa=f;
}
}
t[f].fa=x;//x旋为f的父节点
if(son==1)//左旋，f变为x的左儿子
{
t[x].ls=f;
}
else//右旋，f变为x的右儿子
{
t[x].rs=f;
}
t[x].fa=g;//x现在是祖父的儿子
if(g)//更新祖父的儿子
{
if(t[g].rs==f)
{
t[g].rs=x;
}
else
{
t[g].ls=x;
}
}
Update(f);
Update(x);
}Splay(int x,int goal),把节点x旋转到goal位置。goal=0表示把x旋转到根，x是新的根。goal≠0表示把x旋转为goal的儿子。
Splay Rotate Destiny
void Splay(int x,int goal)
{
if(goal==0)
{
root=x;
}
while(1)
{
int f=t[x].fa;//一次处理x,f,g三个节点
int g=t[f].fa;
if(f==goal){
break;
}
if(g!=goal)//有祖父，分为一字旋和之字旋两种情况
{
if(get(x)==get(f))//一字旋，先旋转f,g
{
rotate(f);
}
else//之字旋，直接旋转x
{
rotate(x);
}
}
rotate(x);
}
Update(x);
} 2.分裂和合并：
Insert()、Del()函数中包含了分裂与合并，详情见代码注释。利用Splay函数实现分裂与合并，编码很简单。
Splay Insert and Delete
void Insert(int L,int len)//插入一段区间
{
int x=kth(root,L);//x为第L个数的位置，y为第L+1个数的位置
int y=kth(root,L+1);
Splay(x,0);//分裂
Splay(y,x);
//先把x旋转到根，然后把y旋转到x的儿子，且y的儿子为空
t[y].ls=build(1,len,y);//合并：建一棵树，挂到y的左儿子上
Update(y);
Update(x);
}
void Del(int L,int R)//删除区间[L+1,R]
{
int x=kth(root,L)；
int y=kth(root,R+1);
Splay(x,0);//y是x的右儿子，y的左儿子是待删除的区间
Splay(y,x);
t[y].ls=0;//剪短左子树，等于直接删除，这里为了简单，没有释放空间
Update(y);
Update(x);
}3.查询：
Splay Find
int kth(int x) { //查询排名为x的数
int now = root;
while (1) {
if (siz[son[now][0]] >= x) now = son[now][0]; //查过头了
else if (siz[son[now][0]] + cnt[now] >= x) return val[now]; //正好查到
else {
x -= (siz[son[now][0]] + cnt[now]);
now = son[now][1]; //没查够
}
}
}Splay Rank
int rank(int x) { //查询x的排名
int now = root, ans = 0;
while (1) {
if (!now) return ans + 1; //树中不存在这个数 那就是目前查到比它小的数的数目+1
if (val[now] > x) now = son[now][0]; //要查的数比now节点的数小 说明在左子树
else if (val[now] == x) {
ans += siz[son[now][0]]; //比它小的数的数目
splay(now);
return ans + 1;
} else { //要查的数在左子树
ans += siz[son[now][0]] + cnt[now]; //此时当前节点和左子树所有数都比它小
now = son[now][1];
}
}
}Splay Find pre/nxt
int findpre() { //查询根节点的前驱对应的结点编号
int now = son[root][0]; //首先进入左子树 因为左子树的所有数都比它小
while (son[now][1]) now = son[now][1]; //然后一直往大的走 找最大的
return now;
}
int findnxt() { //跟上面同理
int now = son[root][1];
while (son[now][0]) now = son[now][0];
return now;
}
···
else if (opt == 5) {
splay.insert(x); //把x先旋到根节点 而且一定要插入而不是直接旋 防止树上本来就没有x
printf("%d\n", splay.val[splay.findpre()]);
splay.del(x); //用完删掉
} else {
splay.insert(x); //同上
printf("%d\n", splay.val[splay.findnxt()]);
splay.del(x);
}注意
（感谢孙宝）
所以 splay 容易写挂的原因找到了 要是哪个 splay 和 maintain 忘写了就寄了
那么怎么记住到底哪要写哪不用写呢
对于 maintain 很简单 改了啥就把它自己 maintain 一下 再把父亲（如果有）也 maintain 一下
对于 splay 实际上我们使用这个函数的同时如果要实现提根的功能 那就写
比如 insert 我们查询前驱后继需要使用它并且把插入的数旋到根 所以要写
比如 rank 我们就是要用它把权值为 x 的结点旋到根节点 所以要写
再比如 del 呃这个你肯定不能忘
如果还记不住怎么办呢
首先要明确 splay 是复杂度的保证 写少了复杂度就会假
但是写几个肯定是没事的
maintain 也是 如果该更新的没更新肯定就寄了
但是把没必要更新的也更新了问题就不大
所以实在不行这俩就是能写就写
当然这么干常数就又会变大 所以最好还是记一下上面那个
