|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <iostream>
|
|
|
#include <algorithm>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 100010, INF = 1e8;
|
|
|
|
|
|
int n;
|
|
|
struct Node {
|
|
|
int l, r; // 左右儿子节点号
|
|
|
int key, val; // BST中的真实值，堆中随机值
|
|
|
int cnt, size; // 当前数字个数,小于等于当前数字的数字个数总和
|
|
|
} tr[N];
|
|
|
|
|
|
int root, idx;
|
|
|
|
|
|
void pushup(int p) {
|
|
|
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt; // BST左子树数字个数+右子树数字个数+自己数字个数
|
|
|
}
|
|
|
|
|
|
int get_node(int key) {
|
|
|
tr[++idx].key = key; //填充 BST的值
|
|
|
tr[idx].val = rand(); //堆中的随机值
|
|
|
tr[idx].cnt = tr[idx].size = 1;
|
|
|
return idx;
|
|
|
}
|
|
|
|
|
|
//右旋
|
|
|
void zig(int &p) {
|
|
|
int q = tr[p].l;
|
|
|
tr[p].l = tr[q].r;
|
|
|
tr[q].r = p;
|
|
|
p = q;
|
|
|
pushup(tr[p].r), pushup(p);
|
|
|
}
|
|
|
|
|
|
//左旋
|
|
|
void zag(int &p) {
|
|
|
int q = tr[p].r;
|
|
|
tr[p].r = tr[q].l;
|
|
|
tr[q].l = p;
|
|
|
p = q;
|
|
|
pushup(tr[p].l), pushup(p);
|
|
|
}
|
|
|
|
|
|
void build() {
|
|
|
get_node(-INF), get_node(INF);
|
|
|
root = 1, tr[1].r = 2;
|
|
|
pushup(root);
|
|
|
if (tr[1].val < tr[2].val) zag(root);
|
|
|
}
|
|
|
|
|
|
void insert(int &p, int key) {
|
|
|
if (!p)
|
|
|
p = get_node(key);
|
|
|
else if (tr[p].key == key)
|
|
|
tr[p].cnt++;
|
|
|
else if (tr[p].key > key) {
|
|
|
insert(tr[p].l, key); //往左边插入
|
|
|
if (tr[tr[p].l].val > tr[p].val) zig(p); //左儿子大，右旋
|
|
|
} else {
|
|
|
insert(tr[p].r, key); //往右边插入
|
|
|
if (tr[tr[p].r].val > tr[p].val) zag(p); //右儿子大，左旋
|
|
|
}
|
|
|
pushup(p);
|
|
|
}
|
|
|
|
|
|
void remove(int &p, int key) {
|
|
|
if (!p) return; //如果发现p==0, 就是没找着
|
|
|
|
|
|
if (tr[p].key == key) { //如果找着了
|
|
|
if (tr[p].cnt > 1) //并且不止1个，这个就简单了，去掉一个就行了,记得 pushup
|
|
|
tr[p].cnt--;
|
|
|
else if (tr[p].l || tr[p].r) { //如果只有1个，并且，有左儿子或右儿子，这时不能直接删除掉，需要处理一下
|
|
|
if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) { //如果没有右儿子，或者是左儿子的随机值大于右儿子随机值，右旋
|
|
|
zig(p); //右旋后，此值向右运动，继续递归右子树处理
|
|
|
remove(tr[p].r, key);
|
|
|
} else {
|
|
|
zag(p); //左旋，此值向左运动，继续递归向左子树处理
|
|
|
remove(tr[p].l, key);
|
|
|
}
|
|
|
} else
|
|
|
p = 0; //左右都没有子树，直接标识为删除
|
|
|
} else if (tr[p].key > key) //如果在左
|
|
|
remove(tr[p].l, key);
|
|
|
else
|
|
|
remove(tr[p].r, key); //如果在右
|
|
|
|
|
|
//向上更新统计信息
|
|
|
pushup(p);
|
|
|
}
|
|
|
|
|
|
int get_rank(int p, int key) { // 通过数值找排名
|
|
|
if (!p) return 0; // 本题中不会发生此情况
|
|
|
if (tr[p].key == key) return tr[tr[p].l].size + 1;
|
|
|
if (tr[p].key > key) return get_rank(tr[p].l, key);
|
|
|
return tr[tr[p].l].size + tr[p].cnt + get_rank(tr[p].r, key);
|
|
|
}
|
|
|
|
|
|
int get_key(int p, int rank) { // 通过排名找数值
|
|
|
if (!p) return INF; // 本题中不会发生此情况
|
|
|
if (tr[tr[p].l].size >= rank) return get_key(tr[p].l, rank);
|
|
|
if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
|
|
|
return get_key(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
|
|
|
}
|
|
|
|
|
|
int get_prev(int p, int key) { // 找到严格小于key的最大数
|
|
|
if (!p) return -INF;
|
|
|
if (tr[p].key >= key) return get_prev(tr[p].l, key);
|
|
|
return max(tr[p].key, get_prev(tr[p].r, key)); //当前位置可能成为答案
|
|
|
}
|
|
|
|
|
|
int get_next(int p, int key) { // 找到严格大于key的最小数
|
|
|
if (!p) return INF;
|
|
|
if (tr[p].key <= key) return get_next(tr[p].r, key);
|
|
|
return min(tr[p].key, get_next(tr[p].l, key));
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
build();
|
|
|
|
|
|
cin >> n;
|
|
|
while (n--) {
|
|
|
int op, x;
|
|
|
cin >> op >> x;
|
|
|
if (op == 1)
|
|
|
insert(root, x);
|
|
|
else if (op == 2)
|
|
|
remove(root, x);
|
|
|
else if (op == 3)
|
|
|
printf("%d\n", get_rank(root, x) - 1);
|
|
|
else if (op == 4)
|
|
|
printf("%d\n", get_key(root, x + 1));
|
|
|
else if (op == 5)
|
|
|
printf("%d\n", get_prev(root, x));
|
|
|
else
|
|
|
printf("%d\n", get_next(root, x));
|
|
|
}
|
|
|
return 0;
|
|
|
} |
