Splay
Splay 树（伸展树），是平衡树的一种，而且可以维护序列，进行一些序列操作。有些序列操作功能甚至是线段树实现不了的（经典的区间翻转）。
维护集合时，Splay 的中序遍历单调递增，而维护序列时，Splay 的中序遍历是维护的序列。
Splay 通过均摊（势能分析）来保证复杂度正确，单次插入，删除，查找操作复杂度为 \(O(\log n)\)
基本思想
Splay 均摊复杂度的基本思想是：每次操作一个节点，都把这个节点通过 Splay 操作伸展到根节点。
写在前面
Splay 代码实现上的一些技巧。
const int N = 1e5 + 5;
struct node
{
int ch[2], fa; // 左右孩子节点，父亲节点的编号
int val, cnt, sz; // 当前节点的值，当前节点有多少个，当前子树的大小
#define lc (t[p].ch[0])
#define rc (t[p].ch[1])
} t[N];
int tot, root;
int new_node(int val) // 新建节点
{
int x = ++tot;
t[x].val = val, t[x].cnt = t[x].sz = 1;
return x;
}
int get(int p) // 判断节点 p 是其父亲的左子节点或右子节点
{
return p == t[t[p].fa].ch[1];
}
void push_up(int p) // 向上传递信息
{
t[p].sz = t[lc].sz + t[rc].sz + t[p].cnt;
}
void clear(int p) // 清空一个节点
{
t[p].ch[0] = t[p].ch[1] = t[p].fa = t[p].val = t[p].cnt = t[p].sz = 0;
}
旋转
Splay 和 Treap 的旋转操作类似但更丰富。可以分为单旋和双旋，双旋又可分为同构调整和异构调整。
单旋
分为左旋与右旋，