Znzryb's Blog
0%

P3369 【模板】普通平衡树

Posted on Edited on

题目大意

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

  1. 插入一个数 x。

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

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

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

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

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

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

参考博客

https://writings.sh/post/fhq-treap

其他OJ

https://loj.ac/p/104

参考视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#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