预备知识：
至于BST，随便看一下就可以，
我们知道二叉搜索树是O(logN)的，那我们为什么要用平衡树呢？
之前我们了解到，BST的插入是小的往左子树走，大的往右子树走，如果凉心出题人给出的序列是有序的呢
这样我们就只能O(N)的操作，GG
旋转(rotate)：
Splay的经典操作就是旋转
在Splay中，我们用旋转来保持平衡，也就是保持是log(N)的量级
旋转就是将节点向上旋转到父亲节点的位置，同时保持平衡
有zig，和zag两种情况（其实都一个样）
具体要怎么旋转呢
如图，X，Y，Z 是三个节点，A，B，C 是三颗子树，我们要把 Z 转到 Y 的位置
其实就只有3步，顺序随意
根据平衡树的性质
Z 是 Y 的左儿子，所以Z < Y
Y 是 X 的左儿子，所以Y < X
我们要把 Z 旋转上去的话，就把 Z 放到 Y 的位置
整完了长这样
因为我们还没操作 Y，所以Y还有连向其父亲和儿子的边
总结一下
Step1：把要旋转的节点放到父亲的位置
而 Y > Z 且 Y < X，所以这时Y就成了Z的右儿子
总结一下
Step2：把要旋转节点的父亲设为其儿子
这时会有三个节点(子树)连向 Z，而Y只有一个儿子，显然，Z，子树 B 和子树 C 都是小于 Y 的，子树 B 大于 Z，所以 B 成为 Y 的左儿子
这样就完成了
总结一下
Step3：把 父节点所占旋转节点的儿子 设为父节点的对应儿子
代码：
定义一波：
struct tree { int fa, cnt, sum, val; //父亲 //计数(几个值为x的点) //以当前点为根节点的子树节点个数 //当前点的值
int ch[2]; //左右儿子，0为左儿子，1为右儿子
} t[N];
关于获得这个节点是左儿子还是右儿子：
inline int get(int x) { return t[t[x].fa].ch[0] == x ? 0 : 1; }
更新：
inline void pushup(int x) { t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].cnt; }
旋转：
inline void rotate(int x) { int fa = t[x].fa, gfa = t[fa].fa;//父亲和爷爷
int k = get(x);//x是其父节点的那个儿子 //step1
t[x].fa = gfa; t[gfa].ch[get(fa)] = x; //step2
t[t[x].ch[k ^ 1]].fa = fa; t[fa].ch[k] = t[x].ch[k ^ 1]; //step3
t[fa].fa = x; t[x].ch[k ^ 1] = fa; pushup(fa), pushup(x); //因为旋转后父节点成了当前点的子节点，所以先更新父亲
}
关于为什么是 k ^ 1，假设我们要旋转的点是左儿子，那他的父亲一定会成为他的右儿子，同理，如果要旋转的点是左儿子，他的父节点一定会成为他的右儿子
伸展(splay)
splay操作就是把一个点旋转到指定的点
最容易想到的，就是一直旋转到指定的节点，然而这样是错的
这时我们就要用到双旋，双旋有两大种四小种情况
1、zig-zig或zag-zag
当节点是父亲的左儿子且父节点是祖父节点的左儿子
或节点是父亲的右儿子且父节点是祖父节点的右儿子
先旋转父亲，再旋转自己
借用一下GeeksofrGeeks的图：
Zig-Zig (Left Left Case):
G P X
/ \ / \ / \
P T4 rightRotate(G) X G rightRotate(P) T1 P
/ \ ============> / \ / \ ============> / \
X T3 T1 T2 T3 T4 T2 G
/ \ / \
T1 T2 T3 T4
Zag-Zag (Right Right Case):
G P X
/ \ / \ / \
T1 P leftRotate(G) G X leftRotate(P) P T4
/ \ ============> / \ / \ ============> / \
T2 X T1 T2 T3 T4 G T3
/ \ / \
T3 T4 T1 T2
2.zig-zag或zag-zig
当节点是父亲的左儿子且父节点是祖父节点的右儿子
或节点是父亲的右儿子且父节点是祖父节点的左儿子
旋转两次自己
再次借用GeeksforGeeks的图：
Zag-Zig (Left Right Case):
G G X
/ \ / \ / \
P T4 leftRotate(P) X T4 rightRotate(G) P G
/ \ ============> / \ ============> / \ / \
T1 X P T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
Zig-Zag (Right Left Case):
G G X
/ \ / \ / \
T1 P rightRotate(P) T1 X leftRotate(P) G P
/ \ =============> / \ ============> / \ / \
X T4 T2 P T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
代码：
inline void splay(int x, int pos) { while (t[x].fa != pos) {//一直旋转成为目标位置的儿子
int fa = t[x].fa, gfa = t[fa].fa; if (gfa != pos) (t[gfa].ch[0] == fa) ^ (t[fa].ch[0] == x) ? rotate(x) : rotate(fa);//判断是哪个儿子并旋转
rotate(x);//无论哪种情况都要旋转x
} if (pos == 0) root = x; }
插入(insert)
对于一个新的值x
如果x等于根的值，从根节点开始比较节点的val值
如果x==val的话，这个点的计数器++，
x小于val的话向左搜，x大于val的话向右搜
如果不存在某个点的val是x，这时我们即使搜到最底端也没有找到，就直接新建这个节点
因为在插入时可能会形成一条链，在最后的时候还要splay一下把新插入的节点转为根
代码：
inline void insert(int x) { int u = root, fa = 0; //当前位置u，父节点fa
while (u && t[u].val != x) { //当u不存在且u的值不等于x。······①
fa = u; //向下找u的儿子，父亲为u
u = t[u].ch[x > t[u].val]; //大于当前位置u向右找，小于向左找
} if (u) t[u].cnt++; //如果有一个节点的值等于x，计数器++
else { u = ++tot; //新节点的位置
if (fa) t[fa].ch[x > t[fa].val] = u; //如果父节点非根
t[u].ch[1] = t[u].ch[