树剖的未来会补的（卑微）。
这里想讲讲平衡树，因为看着高级，可以证明我学过OI。
我们先了解下 \(BST\)，也就是平衡二叉树。
他的概念是，对于每一个非叶子结点，他的左儿子一定小于当前节点，右儿子必定大于当前节点。
类似于如下图，就是一个好看的 \(BST\)：
那我们现在对平衡二叉树有了深入的了解了，我们就开始进行平衡树的讲解。
一：平衡树解决的问题类型：
1.插入（删除）一个数
2.查询某个数的排名
3.查询某个排名所对应的数
4.查询某个数的前驱（后驱）
二：Splay
1.rotate 操作
分为左旋和右旋，我们偷一张图看一下：
我们将 x 右旋，就是将 x 的父亲 (y) 变成 x 的右儿子，x 的右儿子变成 y 的左儿子，x 变为 R 的右儿子。
我们将 y 左旋，得到的结果和上面一样。
那么我们可以轻松写出 rotate 函数了：
inline void rotate(int x) {
int idx = check(x);//x作为y的哪个儿子
int f = tree[x].f, idf = check(f);//y和y作为R的哪个儿子
int sonx = tree[x].son[idx ^ 1];//x的儿子（与x作为的儿子反着）
int ff = tree[f].f;//y的父亲
connect(sonx, f, idx);//将x的儿子变成y的儿子
connect(f, x, idx ^ 1);//将x的父亲变成x的儿子
connect(x, ff, idf);//将x变为原来y的父亲的对应儿子
update(f);
update(x);//修改当前节点子树的大小
}
2.splay 函数
Splay 的核心，不然也不配命名为 splay。
主要就是进行旋转，将 u 转到 v 的上。
那么我们分三种情况：
1.v 是 u 的父亲，如下图：
我们只需要将 u 转一下即可：
2.u 作为 u 的父亲 k 的左（右）儿子， k 也作为 k 的父亲 v 的左（右）儿子，如下图:
我们需要先旋转 k，再旋转 u：
3.u 作为 u 的父亲 k 的左（右）儿子， k 也作为 k 的父亲 v 的右（左）儿子，如下图：
我们需要连选 2 次 u：
那么这样，我们可以很容易得到 splay 函数的代码：
inline void splay(int u, int v) {
int fv = tree[v].f;
while (fv != tree[u].f) {
int fu = tree[u].f;
if (fv == tree[fu].f) rotate(u);//v的父亲是u的父亲的父亲，即v是u的父亲
else if (check(u) == check(fu)) rotate(fu), rotate(u);//u和u的父亲分别同属于他们父亲的同种儿子
else rotate(u), rotate(u);//与上面相反
}
}
3.处理操作
1.插入：
那么是很显然的，只需要判断是否是相同的数即可。
相同的数，直接在频率上加一即可，否则建立新节点。
代码如下：
inline int add(int x, int fa) {
tree[++ siz].data = x;
tree[siz].f = fa;
tree[siz].cnt = tree[siz].sum = 1;
return siz;
}//添加一个节点
void push(int x) {
int sign = 0, nxt;
tot ++;
if (! root) root = add(x, 0);//总得先有根节点吧……
else {
int now = root;
while (now) {
tree[now].sum ++;
if (tree[now].data == x) {
tree[now].cnt ++, sign = now;
break;
} //已经有过这个数字，就将cnt++，位置标记
nxt = tree[now].data < x ? 1 : 0;
if (! tree[now].son[nxt]) {
sign = tree[now].son[nxt] = add(x, now);
break;
}//这个节点还没有数字，就将这个数字差到当前节点
now = tree[now].son[nxt];
}
}
splay(sign, root);
}