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 的旋转操作类似但更丰富。可以分为单旋和双旋，双旋又可分为同构调整和异构调整。

单旋

分为左旋与右旋，