P3369 【模板】普通平衡树 · znzryb

## 题目大意

维护一个动态可重集合 M，需要支持以下操作：

1. 插入一个数 x。

1. 删除一个数 x（若有多个相同值，只删除一个）。

1. 查询集合中严格小于 x 的元素个数，并将结果加 1 输出。

1. 查询集合按从小到大排序后，第 x 小的数。

1. 查询 x 的前驱：小于 x 且最大的数（不保证 x 在集合中，但保证答案存在）。

1. 查询 x 的后继：大于 x 且最小的数（不保证 x 在集合中，但保证答案存在）。

[P3224 [HNOI2012] 永无乡](/2024/10/04/20241004-d95dd83e) 

主要是发现此题寻找第k大的连通块需要平衡二叉树，不学不行，故来学习。

参考博客

[https://writings.sh/post/fhq-treap](https://writings.sh/post/fhq-treap) 

其他OJ

[https://loj.ac/p/104](https://loj.ac/p/104)

参考视频

[https://www.bilibili.com/video/BV1ft411E7JW/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675](https://www.bilibili.com/video/BV1ft411E7JW/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675)

```cpp
#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll MAXN=static_cast<ll>(1e5+10);
int cnt,root;

struct Node {
    int l,r;
    int val;
    int key;
    int size; // size
}fhq[MAXN];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int newnode(int val) {
    fhq[++cnt].val=val;
    fhq[cnt].key=rng();
    fhq[cnt].size=1;
    return cnt;
}

inline void update(int now) {
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}

// 分裂之后左子树全部是比val值<=的，右子树全部是比y>=的
//                         左子树    右子树
void split(int now,int val,int &x,int &y) {
    if(!now) x=y=0;
    else {
        if(fhq[now].val<=val) {
            x=now;
            // 继续分裂右子树，因为左树<=val，无需再进行分裂，右树还需要继续分裂
            split(fhq[now].r,val,fhq[now].r,y);
        }else {
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}

int merge(int x,int y) {
    if(!x||!y) return x+y;
    // 按照二叉堆的性质，y一定再x的下面（大根堆）
    if(fhq[x].key>fhq[y].key) {
        // 按照二叉搜索树，x<y,y在x的右边，综上，y在x的右下
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }else {
        // 按照二叉堆的性质，x一定在y的下面（大根堆）
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}

int x,y,z;

inline void ins(int val) {
    // 按值分裂，将树分为x，y
    split(root,val,x,y);
    // 合并树x，树y，新节点val
    root=merge(merge(x,newnode(val)),y);
}

inline void del(int val) {
    split(root,val,x,z);
    // 此时y树上所有值全部等于val
    split(x,val-1,x,y);
    // 不要y树的根节点，也就是把他的左子树和右子树合并
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}

inline void getrank(int val) {
    split(root,val-1,x,y);
    cout<<fhq[x].size+1<<endl;
    root=merge(x,y);
}

inline void getnum(int rank) {
    int now=root;
    while(now) {
        if(fhq[fhq[now].l].size+1==rank)
            break;
        // 当前节点rank比较大，要找的点在左子树上，令当前节点为左子树
        else if(fhq[fhq[now].l].size>=rank)
            now=fhq[now].l;
        else {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    cout<<fhq[now].val<<endl;
}

inline void pre(int val) {
    split(root,val-1,x,y);
    // 前驱就是分裂出来的x树上最右边的点
    int now=x;
    // 不断向右走直到没有点了
    while (fhq[now].r) {
        now=fhq[now].r;
    }
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

inline void nxt(int val) {
    split(root,val,x,y);
    int now=y;
    while (fhq[now].l)
        now=fhq[now].l;
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) {
        int opt,xopt;
        cin>>opt>>xopt;
        switch (opt) {
            case 1:
                ins(xopt);
                break;
            case 2:
                del(xopt);
                break;
            case 3:
                getrank(xopt);
                break;
            case 4:
                getnum(xopt);
                break;
            case 5:
                pre(xopt);
                break;
            case 6:
                nxt(xopt);
                break;
        }
    }
}
// AC https://www.luogu.com.cn/record/190721203
```