Splay是BST（二叉搜索树）的一种

1. 结构

Splay上的点需要维护左儿子以及右儿子的编号,父亲节点以及这个点的权值（关键码）,这里的模板假设的情况是每个节点的cnt数为1，也就是说没有重复节点。

struct node{
    int s[2];//s[0]表示左儿子，s[1]表示右儿子
    int v;//value
    int p;//parent，记录父亲节点是谁
    int size;
    void init(int _v,int _p){
        v = _v;
        p = _p;
        size = 1;
    }
}tr[N];

2. 旋转操作

首先我们知道一个中序遍历可以对应多个不同的二叉搜索树，因此可以通过旋转操作使我们的树的结构发生变化而保存的信息不发生改变（因为我们的信息是存储在中序遍历中的）

下面是一个在Splay树中的旋转模板，比一般的zig,zag要短上不少

    void rotate(int x){
        int y = tr[x].p;
        //取得x的父节点y
        int z = tr[y].p;
        //取得y的父节点z
        int k = tr[y].s[1]==x;
        //k为0表示x是的左节点，反之则是右节点
        tr[z].s[tr[z].s[1]==y] = x;
        //从上往下修改，先把z的儿子变成x
        tr[y].s[k] = tr[x].s[k^1];tr[tr[x].s[k^1]].p = y;
        //把x的一个儿子给y
        tr[x].s[k^1] = y;tr[y].p = x;
        pushup(y);pushup(x);
    }

3. Splay操作

//把x旋转到k的下面
void splay(int x,int k){
    while(tr[x].p!=k){
        int y = tr[x].p;
        int z = tr[z].p;
        if(z!=k){
            if(tr[z].s[1]==y^tr[y].s[1]==x) rotate(x);//如果x,y,z在一条直线上，旋转y再旋转x,否则旋转两次x
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) root = x;
}

4.Insert操作

int insert(int x){  
    int u = root,p =0;
    while(u){
        p = u;
        u = tr[u].s[x>tr[u].v];
    } 
    u = ++idx;
    if(p) tr[p].s[x>tr[p].v] = u; //只要父节点不是0，就把父节点的儿子更新
    tr[u].init(x,p); //再初始化新结点u
    splay(u,0);
    return u; //返回编号
}

5. Pushup操作（维护子树大小）

    void pushup(int u){
        tr[u].size = tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
    }
    //在函数递归之后调用pushup更新子树大小