替罪羊树

见注释

这种平衡树很好理解，写起来也不难， 尤其注意参数一定要传对
但是我看着AC代码 还是调了好久好久………… QAQ(还是我太弱了)

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100010;
const double alpha = 0.75;    // 啊啊啊   double ！！

struct Scape_goat
{
    int l, r;
    int val;
    int size;   //  子树的大小（包括它自己）， 包括被打了删除标记的结点
    int exist;
    int fact;
}tr[N];
int idx;
int root;
int rec[N], cnt;

// 每次新建节点只管他自己，不需要管儿子们
void build(int &u, int val)
{
    u = ++ idx;   // 开一个位置
    tr[u].val = val;
    tr[u].size = 1;
    tr[u].fact = 1;
    tr[u].exist = true;
}

/** 
 *  重构条件 ：      当前节点的左子树或右子树的size  > 当前结点的大小 乘 一个平衡因子alpha (一般取0.75)
 *               或者以当前结点为根的子树中被删掉的点 > 该子树大小的 30% 
 **/

bool isbalance(int u)
{
    if (tr[tr[u].l].size > tr[u].size * alpha || tr[tr[u].r].size > tr[u].size * alpha)  return false;
    if (tr[u].size - tr[u].fact > tr[u].size * 0.3) return false;
    return true;
}

/**
 * 重构： 将当前子树先中序遍历，  压扁，然后再拎起来
 **/

void inorder(int u)
{
    if (!u) return;
    inorder(tr[u].l);
    if (tr[u].exist) rec[++ cnt] = u;
    inorder(tr[u].r);
}

// pushup 的时候， 由于没有记录子节点到父节点的指针，  所以只能头递归
void pushup(int tmp, int op)
{
    if (!tmp) return;    //  整棵树都被删掉的情况
    if (tr[tmp].val > tr[op].val)
    {
        pushup(tr[tmp].l, op);
    }
    else pushup(tr[tmp].r, op);

    tr[tmp].size = tr[tr[tmp].l].size + tr[tr[tmp].r].size + 1;
    // fact 不需要修改
}

// l, r 指rec数组中存的子树中存在的结点
// u 是l ,r 这段区间所构成子树的根
void lift(int l, int r, int &u)
{
    if (l == r)   // 叶子结点
    {
        u = rec[l];    // 同样 传引用 将这个节点设置为他的父亲节点的儿子
        tr[u].l = tr[u].r = 0;
        tr[u].size = 1;
        tr[u].fact = 1;
        return ;
    }
    int mid = l + r >> 1;    // 找根
    // 因为 该树的定义为 左子树严格小于根， 所以 需要放置 连续mid左侧连续几个数相等的情况
    // 注意这儿的 l ,r mid 并不是结点，  rec[l, r, mid] 才是结点！！！
    while (mid > l and tr[rec[mid]].val == tr[rec[mid - 1]].val) mid --;
    u = rec[mid];
    if (mid == l)   tr[u].l = 0;
    else   lift(l, mid - 1, tr[u].l);   // 注意递归两边的时候传mid - 1 与 mid + 1, 千万不能有mid,  否则可能自己的根是自己，导致递归炸掉

    lift(mid + 1, r, tr[u].r);
    tr[u].size = tr[u].fact = r - l + 1;
}

void rebuild(int &u)
{
    cnt = 0;
    inorder(u);
    if (cnt == 0)   // 这颗子树整体都应该被删掉
    {
        u = 0;      // 即他作为他的父节点的子结点变成了0， 传引用的好书
        return;
    }
    // 否则， 分治 拎起来
    lift(1, cnt, u);
}

/**
 * 检查并判断一棵树是否需要重构
 * 从根节点向当前被操作的结点一路判断，   找到第一个需要被重构的结点，并重构它
 * 注意顺序不能反， 如果反过来找，就可能重构好几次。
 **/

// tmp 是当前的结点， 从root 开始,  op 代指刚被操作过的结点
void check(int &tmp, int op)
{
    if (tmp == op) return;
    if (!isbalance(tmp))
    {
        rebuild(tmp);
        pushup(root, tmp);  // 用子节点的size 更新父节点的size  
        return;
    }
    if (tr[op].val < tr[tmp].val) check(tr[tmp].l, op);
    else check(tr[tmp].r, op);
}

// 左边放小于根的， 右边放 >= 根的
void insert(int &u, int val)  // 上一层传来的参数是 tr[u].l 或 tr[u].r , 传引用相当于直接 修改 tr[u].l = xxx 
{
    if (!u)
    {
        build(u, val);
        check(root, u);
        return;
    }
    tr[u].size ++;
    tr[u].fact ++;
    if (val < tr[u].val) insert(tr[u].l, val);
    else insert(tr[u].r, val);
}

// 懒惰删除， 只打标记不真删， 只减fact 不减 size
void del(int u, int val)
{
    tr[u].fact --;
    if (tr[u].exist and tr[u].val == val)
    {
        tr[u].exist = false;
        check(root, u);
        return;
    }
    if (val < tr[u].val) del(tr[u].l, val);
    else del(tr[u].r, val);
}

// val 不一定存在
int get_rank_by_num(int val)
{
    int tp = root;
    int rank = 1;
    while (tp)
    {
        if (val <= tr[tp].val) tp = tr[tp].l;
        else
        {
            rank += tr[tr[tp].l].fact + tr[tp].exist;
            tp = tr[tp].r;
        }
    }
    return rank;
}

int get_num_by_rank(int k)
{
    int tp = root;
    while (tp)
    {
        if (tr[tr[tp].l].fact + tr[tp].exist == k and tr[tp].exist) break;   
        if (tr[tr[tp].l].fact >= k) 
        {
            tp = tr[tp].l;
        }
        else 
        {
            k -= tr[tr[tp].l].fact + tr[tp].exist;
            tp = tr[tp].r;
        }
    }
    return tr[tp].val;
}

int get_pre(int val)  // 前驱
{
    int k = get_rank_by_num(val);
    return get_num_by_rank(k - 1);
}
int get_next(int val)
{
    // 注意不能  getnum(getrank(val) + 1)   防止 1224 这种情况，  排名x和x + 1可能是同一个数 
    int k = get_rank_by_num(val + 1);
    return get_num_by_rank(k);
}

int main()
{
    int n;
    scanf("%d", &n);
    int opt, x;
    while (n --)    
    {
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            insert(root, x);
        }
        else if (opt == 2)
        {
            del(root, x);
        }
        else if (opt == 3)
        {
            printf("%d\n", get_rank_by_num(x));
        }
        else if (opt == 4)
        {
            printf("%d\n", get_num_by_rank(x));
        }
        else if (opt == 5)
        {   
            printf("%d\n", get_pre(x));
        }
        else if (opt == 6)
        {
            printf("%d\n", get_next(x));
        }
    }

    return 0;
}