平衡树 没有get ！

· · 个人记录

这波，用心的学习一波 Splay （涨姿势了）

旋转规则：

依：Zig

节点 u 是 root

v 是左孩子：右旋

v 是右孩子：左旋

二：Zig_Zig （ v , u 同侧，先 u 再 v）

节点 u 不是 root

v 与 u 同为左孩子： 右旋两次

v 与 u 同为右孩子： 左旋两次

三：Zig_Zag （ v ，u 异侧，先 v 再 u）

节点 u 不是 root

v 是左孩子，u 是右孩子：v 先右旋，再左旋

v 是右孩子，u 是左孩子：v 先左旋，再右旋

接下来放出代码：

struct node{
    int fa,w,cnt,size;
    int son[2]; // 0 为左儿子， 1 为右儿子 
}tree[MAXN]; 
//旋转：
/******************************************/
void updata(int x)
{
    tree[x].size = tree[tree[x].son[0]].size + tree[tree[x].son[1]].size + tree[x].cnt;
}
void rotate(int x)
{
    int y = tree[x].fa;         //fa
    int z = tree[y].fa;         //grandfa
    int k = tree[y].son[1]==x;  //left | right son
    /**这里很巧妙，笔记依下，用双等于代替 if **/
    tree[z].son[tree[z].son[1]==y] = x;
    tree[x].fa = z;
    tree[y].son[k] = tree[x].son[k^1];
    tree[tree[x].son[k^1]].fa = y;
    tree[x].son[k^1] = y;
    tree[y].fa = x;
}
void Splay(int x, int goal)
{
    while(tree[x].fa != goal)
    {
        int y = tree[x].fa;
        int z = tree[y].fa;
        if(z != goal)
            (tree[y].son[1]==x) ^ (tree[z].son[1]==y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if(goal == 0)   root = x;
    updata(x);  updata(y);  //更新子节点数量  
}
// find: 
// 找到 x 所在的位置，转到 root 
/******************************************/
void find(int x)
{
    int u = root;
    if(!u) return;
    while(x!=tree[u].w && tree[u].son[x>tree[u].w])
        u = tree[u].son[x>tree[u].w];
    Splay(u,0);
}
//前驱 & 后继 
// 先 find 
// 前驱为左子树最右点，后继反之
/******************************************/ 
int NEXT(int x, int k)  // k 为 0 时找前驱，为 1 时找后继  
{
    find(x);
    int u = root;
    if((tree[u].w>x&&k) || (tree[u].w<x&&!k))   return u;
    u = tree[u].son[k];
    while(tree[u].son[k^1]) u = tree[u].son[k^1];
    return u;
}
// 应用： 
/******************************************/ 
void insert(int x)
{
    int u = root,fa = 0;
    while(tree[u].w!=x && u)
    {
        fa = u;
        u = tree[u].son[x>tree[u].w];
    }
    if(u)   tree[u].cnt++;
    else{
        u = ++tot;
        if(fa)  tree[fa].son[x>tree[fa].w] = u;
        tree[u].w = x;
        tree[u].fa = fa;
        tree[u].son[1] = tree[u].son[0] = 0;
        tree[u].cnt = tree[u].size = 1;
    }
    Splay(u,0);
}
void Delete(int x)
{
    int last = NEXT(x,0);
    int next = NEXT(x,1);
    Splay(last,0);  Splay(next,last);
    int del = tree[next].son[0];
    if(tree[del].cnt > 0)
    {
        tree[del].cnt--;
        Splay(del,0);
    }
    else    tree[next].son[0] = 0;
}
int kth(int k)
{
    int u = root;
    if(tree[u].size < k)    return 0;
    while(1)
    {
        int Ls = tree[u].son[0];
        if(tree[Ls].size+tree[u].cnt < k)
        {
            k -= (tree[u].cnt+tree[Ls].size);
            u = tree[u].son[1];
        }
        else if(tree[Ls].size >= k) u = Ls;
        else return tree[u].w;
    }
}
int Search(int x)   // x 的排名 
{
    find(x);
    return tree[tree[root].son[0]].size;
}

int main(void)  //虽然不知道为什么，但依定要先 insert 两个最值，不然会 T 
{               //这样的话 kth(x+1) 才是答案 
    insert(-0x7fffffff);
    insert( 0x7fffffff);
    return 0;
}