Tyvj1728 普通平衡树(splay | 非旋treap | 树状数组 | 宗法树 | vector)

发表于 更新于 分类于

题目

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

1
2
3
106465
84185
492737

HINT

  1. n的数据范围：n<=100000
  2. 每个数的数据范围：[-2e9,2e9]

题解

这道题是平衡树的模板题，是平衡树都能用，我用了三种方法写

BST二叉排序树或平衡树具有以下性质： 1. 若左子树不为空，则左子树所有结点的值都小于等于它根结点的值 2. 若右子树不为空，则右子树所有结点的值都大于等于它根结点的值 3. 左右子树也分别为二叉排序树

伸展树 Splay

可以通过旋转来更换结点位置

插入 insert

从根结点开始，如果比x大则向左，如果比x小就向右，如果相等则增加其count的值，没有就新建一个结点

删除 erase

从根结点开始，找到该点，splay到根结点，若count大于1则自减，其余情况： 1. 没有子结点，删除根结点，令root=nullptr 2. 有左或右儿子，令root为该儿子，删除该结点 3. 两个儿子都有，将右子树最小结点splay到根的右儿子，令根的左儿子成为右儿子的左儿子，删除该结点

查询x的排名 rank

从根结点开始，找到该点，splay到根结点，返回左子树size加上1

从根结点开始，若左儿子size大于等于x，向左走，若加上该结点size小于x向右走，若为该结点则返回

前驱 predeccessor

插入x，splay到根结点，返回左子树最大值，删除x

后继 successor

插入x,splay到根结点，返回右子树最小值，删除x

完整代码 code

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include<cstdio>
using namespace std;
int f(-1);
inline char GetCharacter() {
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) &&
           (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
           EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
    f = 1, x = 0;
    static char c = GetCharacter();
    while (!IS_DIGIT(c)) {
        if (c == '-') f = -1;
        c = GetCharacter();
    }
    while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
    x *= f;
}
#undef IS_DIGIT
class splay_tree {
    private:
        struct node {
            int value, size, count;
            node *left, *right, *father;
            node(const int v = 0) {
                value = v, size = 1, count = 1;
                left = right = father = NULL;
            }
        }*root;
        inline void update(register node *x) {
            if (x) x->size = x->count + 
             (x->left ? x->left->size : 0) + 
             (x->right ? x->right->size : 0);
        }
        inline void left_rotate(register node *x) {
            register node *y = x->father;
            y->right = x->left;
            if (x->left) x->left->father = y;
            x->father = y->father;
            if (y->father) {
                if (y == y->father->left) y->father->left = x;
                else y->father->right = x;
            }
            x->left = y;
            y->father = x;
            update(y);
            update(x);
        }
        inline void right_rotate(register node *x) {
            register node *y = x->father;
            y->left = x->right;
            if (x->right) x->right->father = y;
            x->father = y->father;
            if (y->father) {
                if (y == y->father->right) y->father->right = x;
                else y->father->left = x;
            }
            x->right = y;
            y->father = x;
            update(y);
            update(x);
        }
        inline void splay(register node *x,const node *target=NULL) {
            register node *y;
            while (x->father != target) {
                y = x->father;
                if (x == y->left) {
                    if (y->father != target && y == y->father->left) right_rotate(y);
                    right_rotate(x);
                } else {
                    if (y->father != target && y == y->father->right) left_rotate(y);
                    left_rotate(x);
                }
            }
            if (!target) root = x;
        }
        inline node *find(const int &key) {
            register node *x = root;
            while (1) {
                if (!x) break;
                else if (x->value == key)break;
                if (x->value < key) x = x->right;
                else if (x->value > key) x = x->left;
            }
            if (x) splay(x);
            return x;
        }
        inline node *subtree_maximum(register node *x) {
            if (!x) return NULL;
            while (x->right) x = x->right;
            return x;
        }
        inline node *subtree_minimum(register node *x) {
            if (!x) return NULL;
            while (x->left) x = x->left;
            return x;
        }
    public:
        inline void insert(const int &key) {
            register node *x = root, *y = NULL;
            while (1) {
                if (!x) break;
                else if (x->value == key) break;
                y = x;
                if (x->value < key) x = x->right;
                else if (x->value > key) x = x->left;
            }
            if (x) ++x->count, ++x->size;
            else {
                x = new node(key);
                x->father = y;
                if (y) {
                    if (x->value > y->value) y->right = x;
                    else y->left = x;
                }
            }
            if (!y) root = x;
            update(y);
            splay(x);
        }
        inline void erase(const int &key) {
            register node *x = find(key);
            if (x) {
                if (x->count > 1) --x->count, --x->size;
                else {
                    if (!x->left && !x->right) {
                        delete root;
                        root = NULL;
                        return;
                    } else if (!x->left) {
                        root = x->right;
                        root->father = NULL;
                        delete x;
                        return;
                    } else if (!x->right) {
                        root = x->left;
                        root->father = NULL;
                        delete x;
                        return;
                    } else {
                        register node *y = subtree_minimum(x->right);
                        splay(y, x);
                        y->left = x->left, x->left->father = y;
                        y->father = NULL;
                        delete x;
                        root = y;
                        update(y);
                    }
                }
            }
        }
        inline int rank(const int &key) {
            register node *x = find(key);
            if (x) return (((x->left ? x->left->size : 0 ) + 1));
            else return 0;
        }
        inline int search(register int rnk) {
            register node *x = root;
            while(1) {
                if (x->left) {
                    if (x->left->size < rnk && x->left->size + x->count >= rnk) break;
                    else if (x->left->size >= rnk) x = x->left;
                    else rnk -= x->left->size + x->count, x = x->right;
                } else {
                    if (x->count >= rnk) break;
                    else rnk -= x->count, x = x->right;
                }
            }
            return x->value;
        }
        inline int predeccessor(const int &key) {
            insert(key);
            register node *ret = subtree_maximum(root->left);
            splay(ret);
            erase(key);
            return ret->value;
        }
        inline int successor(const int &key) {
            insert(key);
            register node *ret = subtree_minimum(root->right);
            splay(ret);
            erase(key);
            return ret->value;
        }
};
int n, opt, x;
splay_tree tree;
int main(int argc, char **argv) {
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &opt, &x);
        switch(opt) {
            case 1: {
                tree.insert(x);
                break;
            }
            case 2: {
                tree.erase(x);
                break;
            }
            case 3: {
                printf("%d\n", tree.rank(x));
                break;
            }
            case 4: {
                printf("%d\n", tree.search(x));
                break;
            }
            case 5: {
                printf("%d\n", tree.predeccessor(x));
                break;
            }
            case 6: {
                printf("%d\n", tree.successor(x));
                break;
            }
        }
    }
    return 0;
}

非旋树堆 FHQ Treap

只有两个操作，能够实现可持久化

分离 split

按键值将tree分为x，y两棵树（也可按权值）

合并 merge

按权值将两棵树合并为一棵树

插入 insert

将原树分为x，y两棵树，将新节点看成一棵树与x合并，再与y合并

删除 erase

首先我们把树分为x和z两部分

那么x树中的最大权值为a

再把x分为x和y两部分。

此时x中的最大权值为a-1，且权值为a的节点一定是y的根节点。

然后我们可以无视y的根节点，直接把y的左右孩子合并起来，这样就成功的删除了根节点，

最后再把x，y，z合并起来就好

其他操作见代码

完整代码 code

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
#include<cstdio>
#include<cstdlib>
using namespace std;
int f(-1);
inline char GetCharacter() {
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) &&
           (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
           EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
    f = 1, x = 0;
    static char c = GetCharacter();
    while (!IS_DIGIT(c)) {
        if (c == '-') f = -1;
        c = GetCharacter();
    }
    while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
    x *= f;
}
#undef IS_DIGIT
class fhq_treap {
    private:
        struct node {
            node *left, *right;
            int value, prize, size;
            node(const int v = 0) {
                left = right = NULL;
                value = v, prize = rand(), size = 1;
            }
        }*root, *x, *y, *z;
        int size;
        inline void update(register node *x) {
            x->size = 1 + (x->left ? x->left->size : 0) + 
                    (x->right ? x->right->size : 0);
        }
        inline node *new_node(const int v = 0) {
            ++size;
            register node *tmp = new node(v);
            return tmp;
        }
        inline node *merge(register node *x, register node *y) {
            if (!x) return y;
            if (!y) return x;
            if (x->prize < y->prize) {
                x->right = merge(x->right, y);
                update(x);
                return x;
            } else {
                y->left = merge(x, y->left);
                update(y);
                return y;
            }
        }
        inline void split(register node *now,const int k,register node *&x,
                                                     register node *&y) {
            if (!now) x = y = NULL;
            else {
                if (now->value <= k) x = now, split(now->right, k, now->right, y);
                else y = now, split(now->left, k, x, now->left);
                update(now);
            }
        }
        inline node *kth(register node *now, register int k) {
            while(1) {
                if (now->left != NULL) {
                    if (k <= now->left->size) now = now -> left;
                    else if (k == (now->left ? now->left->size : 0) + 1) return now;
                    else k -= (now->left ? now->left->size : 0) + 1, now = now->right;
                } else if (k == (now->left ? now->left->size : 0) + 1) return now;
                else k -= (now->left ? now->left->size : 0) + 1, now = now->right;
            }
        }
    public:
        fhq_treap() {
            size = 0;
            root = NULL;
        }
        inline void insert(const int &key) {
            split(root, key, x, y);
            root = merge(merge(x, new_node(key)), y);
        }
        inline void erase(const int &key) {
            split(root, key, x, z);
            split(x, key - 1, x, y);
            y = merge(y->left, y->right);
            root = merge(merge(x, y), z);
        }
        inline int rank(const int key) {
            split(root, key - 1, x, y);
            register int ret = (x ? x->size : 0) + 1;
            root = merge(x, y);
            return ret;
        }
        inline int search(const int &rnk) {
            return kth(root, rnk)->value;
        }
        inline int predeccessor(const int &key) {
            split(root, key - 1, x, y);
            register int ret(kth(x, x->size)->value);
            root = merge(x, y);
            return ret;
        }
        inline int successor(const int &key) {
            split(root, key, x, y);
            register int ret(kth(y, 1)->value);
            root = merge(x, y);
            return ret;
        }
};
int n, opt, x;
fhq_treap tree;
int main(int argc, char **argv) {
    Read(n);
    while(n--) {
        scanf("%d %d", &opt, &x);
        Read(opt), Read(x);
        switch(opt) {
            case 1: {
                tree.insert(x);
                break;
            }
            case 2: {
                tree.erase(x);
                break;
            }
            case 3: {
                printf("%d\n", tree.rank(x));
                break;
            }
            case 4: {
                printf("%d\n", tree.search(x));
                break;
            }
            case 5: {
                printf("%d\n", tree.predeccessor(x));
                break;
            }
            case 6: {
                printf("%d\n", tree.successor(x));
                break;
            }
        }
    }
    return 0;
}

宗法树

这是一个非常毒瘤的数据结构，因其删除操作特点而得名

它的特点有： 1. 叶节点存的是数，非叶节点存的是左右两棵子树的最大值 2. 非叶节点左子树的值都比右子树的值小 3. 非叶节点必有左右两棵子树

插入 insert

若无结点则新建，若有，根据性质找到一个叶结点，新建两个子结点，按顺序排这两个数，更新原结点

删除 erase

找到该点，用另一子结点将父亲覆盖

其他操作见代码

完整代码 code

洛谷最新数据会被卡掉一个点

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
#include<cstdio>
#include<algorithm>
using namespace std;
int f(-1);
inline char GetCharacter() {
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) &&
           (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
           EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
    f = 1, x = 0;
    static char c = GetCharacter();
    while (!IS_DIGIT(c)) {
        if (c == '-') f = -1;
        c = GetCharacter();
    }
    while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
    x *= f;
}
#undef IS_DIGIT
class patriarchal_tree {
    private:
        struct node {
            int val, size;
            node *left, *right, *father;
            node(const int v = 0) {
                val = v, size = 1, left = right = father = NULL;
            }
        }*root;
        inline void update(register node *x){
            if (x && x->left) x->val = max(x->left->val, x->right->val), 
                        x->size = x->left->size + x->right->size;
        }
        inline bool isleaf(const node *x){
            return x->left == NULL;
        }
        inline void Insert(const int &v,register node *s){
            if (!s) {
                s = new node(v);
                root = s;
                return;
            }else if (!s->left) {
                s->left = new node (min(s->val , v));
                s->right = new node(max(s->val , v));
                s->left->father = s->right->father = s;
                update(s);
                return;
            }
            if (v > s->left->val) {
                Insert(v, s->right);
            } else Insert(v, s->left);
            update(s);
        }
        inline void Erase(const int &v,register node *s){
            if (isleaf(s)) {
                register node *p = s->father, *t;
                if (!p) {
                    root = NULL;
                    delete s;
                }
                else if (p->right == s) {
                    t = p->left;
                    if (p->left->left) {
                        p->left->left->father = p->left->right->father = p;
                    }
                    p->val = p->left->val, p->size = p->left->size;
                    p->left = t->left, p->right = t->right;
                    delete t;
                    delete s;
                }
                else {
                    t = p->right;
                    if (p->right->left) {
                        p->right->left->father = p->right->right->father = p;
                    }
                    p->val = p->right->val, p->size = p->right->size;
                    p->right = t->right, p->left = t->left;
                    delete t;
                    delete s;
                }
                return;
            }
            if (v > s->left->val) {
                Erase(v, s->right);
            }else Erase(v, s->left);
            update(s);
        }
        inline int Rank(const int &v,const node *s){
            if (isleaf(s)) {
                if (s->val < v) return 2;
                return 1;
            }
            if(v > s->left->val) return Rank(v, s->right) + s->left->size;
            else return Rank(v, s->left);
        }
        inline int Search(register int v,const node *s){
            if (isleaf(s)) return s->val;
            else if (v > s->left->size) return Search(v - s->left->size, s->right);
            else return Search(v, s->left);
        }
    public:
        patriarchal_tree(){
            root = NULL;
        }
        inline void insert(const int &v){
            Insert(v, root);
        }
        inline void erase(const int &v){
            Erase(v, root);
        }
        inline int rank(const int &v){
            return Rank(v, root);
        }
        inline int search(const int &v){
            return Search(v, root);
        }
        inline int predecessor(const int &v){ 
            return Search(Rank(v, root) - 1, root);
        }
        inline int successor(const int &v){
            return Search(Rank(v + 1, root), root);
        }
};
patriarchal_tree T;
int n, opt, x;
int main(int argc, char **argv){
    Read(n);
    while (n--) {
        Read(opt), Read(x);
        if (opt == 1) T.insert(x);
        else if (opt == 2) T.erase(x);
        else if (opt == 3) printf("%d\n", T.rank(x));
        else if (opt == 4) printf("%d\n", T.search(x));
        else if (opt == 5) printf("%d\n", T.predecessor(x));
        else if (opt == 6) printf("%d\n", T.successor(x));
    }
    return 0;
}

2018.7.24更新

vector解法

突然想起来可以用vector过，虽然非常暴力但真的过了

代码 code

比指针版的非旋Treap还快(可能是我写的有毛病)

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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int f(-1);
inline char GetCharacter() {
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) &&
           (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
           EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
    f = 1, x = 0;
    static char c = GetCharacter();
    while (!IS_DIGIT(c)) {
        if (c == '-') f = -1;
        c = GetCharacter();
    }
    while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
    x *= f;
}
#undef IS_DIGIT
vector<int> v;
int n, opt, x;
int main(int argc, char **argv) {
    scanf("%d", &n);
    v.reserve(n + 5);
    while (n--) {
        scanf("%d %d", &opt, &x);
        switch(opt) {
            case 1:
                v.insert(upper_bound(v.begin(), v.end(), x), x);
                break;
            case 2:
                v.erase(lower_bound(v.begin(), v.end(), x));
                break;
            case 3:
                printf("%d\n", lower_bound(v.begin(), v.end(), x) - v.begin() + 1);
                break;
            case 4:
                printf("%d\n", v[x - 1]);
                break;
            case 5:
                printf("%d\n", *--lower_bound(v.begin(), v.end(), x));
                break;
            case 6:
                printf("%d\n", *upper_bound(v.begin(), v.end(), x));
        }
    }
    return 0;
}

2018.8.17更新

树状数组 fenwick tree

又一个令马制烯的方法，但对于平衡树的题树状数组估计也就只能干这个了，不过跑得飞快

离散化 Discretization

为了节省内存，我们在这里进行离散化，当然如果数据范围过大则必须进行离散化

当然离散化后就只能离线做了

离散化后排序去重，为了方便可以使用STL

修改 Add

树状数组基本操作，不再解释

求和 GetSum

树状数组基本操作，不再解释

插入 Insert

将x离散化后的数作为下标，在树状数组对应的地方增加1

删除 Erase

将x离散化后的数作为下标，在树状数组对应的地方减去1

查询排名 Rank

求当前树状数组中下标小于DISCRETE(x)的前缀和

查询排名为x的数 Search

这里是树状数组解法中最困难的一个，用到了倍增的思想

当我们把fenwick_tree[i]的下标加上1 << k后，

fenwick_tree[i + (1 << k)]的值就是我们增加的这一段区间元素的个数

就可以直接判断当前元素个数是否超过了rank，超过了就退回去，否则就保存

求x的前驱 Predecessor

找到比该数排名小1的数

求x得后继 Successor

与求前驱同理

完整代码 Code

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
#include<cstdio>
#include<algorithm>
using namespace std;
int f(-1);
inline char GetCharacter() {
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) &&
           (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
           EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
    f = 1, x = 0;
    static char c = GetCharacter();
    while (!IS_DIGIT(c)) {
        if (c == '-') f = -1;
        c = GetCharacter();
    }
    while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
    x *= f;
}
#undef IS_DIGIT
#define LOWBIT(i) ((i) & (-i))
int fenwick_tree[100010], tree_size;
int table[100010], number_quantity;
inline void Add(register int index, const int &delta) {
  while (index <= tree_size) {
    fenwick_tree[index] += delta;
    index += LOWBIT(index);
  }
}
inline int GetSum(register int index) {
  register int ret(0);
  while (index) {
    ret += fenwick_tree[index];
    index -= LOWBIT(index);
  }
  return ret;
}
inline void Discretization() {
  sort(table + 1, table + number_quantity + 1);
  tree_size = unique(table + 1, table + number_quantity + 1) - (table + 1);
}
#define DISCRETE(x) lower_bound(table + 1, table + tree_size + 1, x) - table
inline void Insert(const int &key) {
  Add(DISCRETE(key), 1);
}
inline void Erase(const int &key) {
  Add(DISCRETE(key), -1);
}
inline int Rank(const int &key) {
  return GetSum(DISCRETE(key) - 1) + 1;
}
inline int Search(register int rank) {
  register int ret(0);
  for (register int i(20); i >= 0; --i) {
    ret += 1 << i;
    if(ret >= tree_size || fenwick_tree[ret] >= rank) ret -= 1 << i;
    else rank -= fenwick_tree[ret];
  }
  return table[++ret];
}
inline int Predeccessor(const int &key) {
  return Search(GetSum(DISCRETE(key) - 1));
}
inline int Successor(const int &key) {
  return Search(GetSum(DISCRETE(key)) + 1);
}
#undef LOWBIT
int n, opt[100010], x[100010];
int main(int argc, char **argv) {
  Read(n);
  for (register int i(1); i <= n; ++i) {
    Read(opt[i]), Read(x[i]);
    if (opt[i] != 4) table[++number_quantity] = x[i];
  }
  Discretization();
  for (register int i(1); i <= n; ++i) {
    switch(opt[i]) {
      case 1: {
        Insert(x[i]);
        break;
      }
      case 2: {
        Erase(x[i]);
        break;
      }
      case 3: {
        printf("%d\n", Rank(x[i]));
        break;
      }
      case 4: {
        printf("%d\n", Search(x[i]));
        break;
      }
      case 5: {
        printf("%d\n", Predeccessor(x[i]));
        break;
      }
      case 6: {
        printf("%d\n", Successor(x[i]));
        break;
      }
    }
  }
  return 0;
}