二叉搜索树

www.luogu.com.cn

定义

二叉搜索树（Binary Search Tree\text{Binary Search Tree}）是一种形状如二叉树的数据结构，用于快速查找和增加删除操作，它有如下几个特殊性质：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

对于一个二叉搜索树，进行操作所花费的平均时间和这个二叉树的高度成正比。对于一个有 nn 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(log⁡n)O(\log n)，最坏为 O(n)O(n)。

操作过程

定义

对于一个二叉搜索树的每一个节点，都要存储以下几样东西：

  1. 左子树节点和右子树节点：l 和 r
  2. 这一个节点上存储的权值：val
  3. 表示这个节点权值出现次数的计数器：cnt
  4. 代表这个树上的大小（即子树和自己大小之和）：size
1
2
3
4
5
6
struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];

与此同时，由于操作中需要不断插入新的数，因此还需要两个变量分别储存树的下标和当前的下标，我们用 root 和 idx 表示：

1
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

创建新节点

创建一个新的节点就是将这个节点全部初始化，同时返回原来的下标值：

1
2
3
4
5
6
int new_node(int k)                    // 创建新节点
{
    tr[idx].val = k;                // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

上传信息

像线段树一样，二叉搜索树同样也有需要维护的信息：每个子树的本身大小，有二叉树的性质可得出：

tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt\text{tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt} 

1
2
3
4
void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

初始化

为了防止有时候询问的二叉搜索树为空，我们可以先在树中加入两个哨兵：-INF\text{-INF} 和 INF\text{INF}，在不断的插入中，他们会始终在树的左右两端，从而有效防止查询越界。

1
2
3
4
5
6
void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

插入

根据二叉搜索树的性质可得，对于每个节点 uu 以及要插入的权值 kk，可以分为四种情况：

  1. u=ku = k 时，直接在该节点的计数变量上 cnt ++。
  2. u<ku < k 时，递归到该节点的右子树节点继续插入。
  3. u>ku > k 时，递归到该节点的左子树节点继续插入。
  4. u=0u = 0 时，则说明没有这个节点，直接利用 idx 创建一个。

tips\bold tips：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);  // 向左递归
            else insert(tr[u].r, k);                // 向右递归
        }
    }
    pushup(u);                              // 上传信息
}

删除

原理和插入相似，不多赘述，一共五种情况：

  1. u=ku = k 时，直接在该节点的计数变量上 cnt --。
  2. uu 节点为叶子节点时，直接 u = 0。
  3. u<ku < k 时，递归到该节点的右子树节点继续删除。
  4. u>ku > k 时，递归到该节点的左子树节点继续删除。
  5. u=0u = 0 时，则说明没有这个节点，直接 return 掉 。

tips\bold tips：在递归完之后要 pushup 一遍，从而维护每个子树的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);  // 如果有右子树，向右递归
                else del(tr[u].l, k);           // 否则向左递归
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

找前驱

一个数 xx 的前驱被定义为小于 xx 的最大的数。

对于一个节点 uu 的权值以及权值 kk，它的查询分为以下三种情况：

  1. u=0u = 0 时，此时说明找到了最左端，应当 return -INF。
  2. u≥ku \ge k 时，说明 $k $的前驱还可能在当前节点的左子树，向左递归。
  3. 其余的情况则说明 u≤ku \le k，此时分为两种情况，一是前驱就是 uu，二是前驱在右子树当中，因此在两者中取 max⁡\max。
1
2
3
4
5
6
int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

找后驱

一个数 xx 的后驱被定义为大于 xx 的最小的数。

原理同上

1
2
3
4
5
6
int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

通过排名找权值

排名定义为比当前数小的数的个数 +1+1。若有多个相同的数，应输出最小的排名。

对于一个节点 uu 以及 rankrank 值，可以分为以下四种情况：

  1. tr[u].val=0\text{tr[u].val} = 0 时，说明这个权值无限大，返回 INF\text{INF}。
  2. tr[tr[u].l].size ≥rank\text{tr[tr[u].l].size } \ge \text{rank}，说明权值在左子树里面，向左递归。
  3. tr[tr[u].l].size + tr[u].cnt≥rank\text{tr[tr[u].l].size + tr[u].cnt} \ge \text{rank}，由于上面的限制条件，说明该节点权值即为答案。
  4. 否则向右进行递归，并且注意右子树中的 $rank $ 值是相对的。
1
2
3
4
5
6
7
int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

通过权值找排名

原理和上面反过来差不多

1
2
3
4
5
6
7
int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

模板代码

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
// Problem: P5076 【深基16.例7】普通二叉树（简化版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5076
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 2147483647;

struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k)                    // 创建新节点
{
    tr[++ idx].val = k;             // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k) insert(tr[u].l, k);  // 向左递归
            else insert(tr[u].r, k);                // 向右递归
        }
    }
    pushup(u);                              // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r) del(tr[u].r, k);  // 如果有右子树，向右递归
                else del(tr[u].l, k);           // 否则向左递归
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 5) insert(root, k);
        else if (op == 1)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1<< '\n';
            del(root, k);
        }
        else if (op == 2) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 3) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}

平衡树

www.luogu.com.cn

www.luogu.com.cn

定义

平衡树简介

使用搜索树的目的之一是 缩短插入、删除、修改和查找（插入、删除、修改都包括查找操作）节点的时间。 关于查找效率，如果一棵树的高度为 hh，在最坏的情况，查找一个关键字需要对比 hh 次，查找时间复杂度（也为平均查找长度 ASL，Average Search Length\text{ASL，Average Search Length}）不超过 O(h)O(h)。一棵理想的二叉搜索树所有操作的时间可以缩短到 O(log⁡n)O(\log n)（nn 是节点总数）。 然而 O(h)O(h) 的时间复杂度仅为理想情况。在最坏情况下，搜索树有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，所有操作（增删改查）的时间是 O(n)O(n)。 可以发现操作的复杂度与树的高度 hh 有关。由此引出了平衡树，通过一定操作维持树的高度（平衡性）来降低操作的复杂度。

一个平衡树有如下几个定义：

  1. 它是一个二叉搜索树
  2. 对于任意一个节点的子树，每一个节点的左子树和右子树的高度差最多为 11。

旋转Treap

简介

Treap\text{Treap}（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree\text{tree}（树）和 heap\text{heap}（堆）的组合。

其中对于堆的性质是：

  • 子节点值（priority\textit{priority}）比父节点大或小（取决于是小根堆还是大根堆）。

https://oi-wiki.org/ds/images/treap-treap-example.svg

操作过程

旋转

旋转 Treap\text{Treap}通过 左旋 和 右旋 的方式维护平衡树的平衡，通过调整堆的优先级从而达到平衡操作。

旋转操作的含义：

  • 在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点（如左旋，就是把右子树变成根节点）
  • 不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点（如左旋，旋转完之后的左子节点是旋转前的根节点）

https://oi-wiki.org/ds/images/treap-rotate.svg

代码思路需要慢慢悟出来

1
2
3
4
5
6
7
8
9
10
11
12
13
void zig(int &u)                            // 右旋
{
    int v = tr[u].l;                        // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u);             // 上传标记
}

void zag(int &u)                            // 左旋
{
    int v = tr[u].r;                        // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u);             // 上传标记
}

插入

和二叉搜索树差不多，只不过要在插入的过程中维护好堆的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k);     // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u); // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k);     // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u); // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);                              // 上传信息
}

删除

同样维护好堆的性质

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
void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key) // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u);             // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u);             // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

模板代码

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
153
154
155
156
157
158
159
160
161
162
163
// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e5 + 9;
const int INF = 0x3f3f3f3f;

struct BST
{
    int l, r;       // 左右子树节点
    int val, key;   // val: 这一个节点上存储的权值  key: 随机数以满足堆的性质
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];
int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int new_node(int k)                    // 创建新节点
{
    tr[++ idx].val = k;             // 将权值修改
    tr[idx].key = rand();           // 给key赋予一个随机数
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

void zig(int &u)                            // 右旋
{
    int v = tr[u].l;                        // v是节点u的左子节点
    tr[u].l = tr[v].r, tr[v].r = u, u = v;  // 依次更新节点
    pushup(tr[u].r), pushup(u);             // 上传标记
}

void zag(int &u)                            // 左旋
{
    int v = tr[u].r;                        // v是节点u的右子节点
    tr[u].r = tr[v].l, tr[v].l = u, u = v;  // 依次更新节点
    pushup(tr[u].l), pushup(u);             // 上传标记
}

void insert(int &u, int k)
{
    if (u == 0) u = new_node(k);            // 如果节点为0，则直接新建一个
    else
    {
        if (tr[u].val == k) tr[u].cnt ++;   // 如果相等，则在计数器上加一个
        else
        {
            if (tr[u].val > k)
            {
                insert(tr[u].l, k);     // 向左递归
                if (tr[tr[u].l].key > tr[u].key) zig(u); // 如果不满足堆的性质，右旋
            }
            else
            {
                insert(tr[u].r, k);     // 向右递归
                if (tr[tr[u].r].key < tr[u].key) zag(u); // 如果不满足堆的性质，左旋
            }
        }
    }
    pushup(u);                              // 上传信息
}

void del(int &u, int k)
{
    if (u == 0) return ;                // 如果节点为0，直接return
    if (tr[u].val == k)                 // 如果权值相等，分三类讨论
    {
        if (tr[u].cnt > 1) tr[u].cnt --;        // 计数器大于1时，直接剪掉
        else 
        {
            if (tr[u].l || tr[u].r)             // 不是叶子节点时
            {
                if (!tr[u].r || tr[tr[u].l].key > tr[tr[u].r].key) // 有右子树或者左子树的key大于右子树的key
                {
                    zig(u);             // 右旋
                    del(tr[u].r, k);    // 向右递归
                }
                else 
                {
                    zag(u);             // 左旋
                    del(tr[u].l, k);    // 否则向左递归
                }
            }
            else u = 0;         // 是叶子节点直接改为0
        }
    }
    else if (tr[u].val > k) del(tr[u].l, k);    // 向左递归
    else del(tr[u].r, k);                       // 向右递归
    pushup(u);                      // 上传信息
}

int get_rank_by_val(int u, int k)
{
    if (u == 0) return 0;       // 如果不存在这个节点，则直接返回0
    if (tr[u].val == k) return tr[tr[u].l].size + 1;        // 如果节点权值等于k，返回这个排名的大小+1
    if (tr[u].val > k) return get_rank_by_val(tr[u].l, k);  // 如果节点权值大于k，则向左侧递归查找
    return tr[tr[u].l].size + tr[u].cnt + get_rank_by_val(tr[u].r, k);  // 否则应该向右递归，并且加上左子树和节点的大小之和
}

int get_val_by_rank(int u, int rank)
{
    if (u == 0) return INF;     // 如果不存在这个节点，说明超出了最大值，返回INF
    if (tr[tr[u].l].size >= rank) return get_val_by_rank(tr[u].l, rank);    // 如果左子树的大小大于rank值，则说明权值在左子树里面，向左递归
    if (tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].val;             // 如果左子树的大小加上当前节点数大于rank值，收到前面条件的限制，说明val值为答案
    return get_val_by_rank(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);   // 否则向右递归，并且向右递归时的rank值是相对于右子树的
}

int get_prev(int u, int k)            // 找前驱
{
    if (u == 0) return -INF;        // 如果节点不存在，则直接返回-INF
    if (tr[u].val >= k) return get_prev(tr[u].l, k);    // k小于当前权值，向左递归
    return max(get_prev(tr[u].r, k), tr[u].val);        // 否则在两者之中取最大值
}

int get_next(int u, int k)            // 找后驱
{
    if (u == 0) return INF;         // 如果节点不存在，则直接返回INF
    if (tr[u].val <= k) return get_next(tr[u].r, k);    // k大于当前权值，向右递归
    return min(get_next(tr[u].l, k), tr[u].val);        // 否则在两者之中取最小值
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    build();
    int n; cin >> n;
    while (n --)
    {
        int op, k; cin >> op >> k;
        if (op == 1) insert(root, k);
        else if (op == 2) del(root, k);
        else if (op == 3)
        {
            insert(root, k);
            cout << get_rank_by_val(root, k) - 1<< '\n';
            del(root, k);
        }
        else if (op == 4) cout << get_val_by_rank(root, k + 1) << '\n';
        else if (op == 5) cout << get_prev(root, k) << '\n';
        else cout << get_next(root, k) << '\n';
    }
    return 0;
}