|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <algorithm>
|
|
|
#include <iostream>
|
|
|
|
|
|
//普通Treap 316 ms
|
|
|
// FHQ Treap 433 ms
|
|
|
//两者基本在一个数量级上，常数略大
|
|
|
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
const int N = 1e5 + 10;
|
|
|
|
|
|
struct Node {
|
|
|
int l, r; //左右儿子的节点号
|
|
|
int key; // BST中的真实值
|
|
|
int val; //堆中随机值,用于防止链条化
|
|
|
int size; //小于等于 key的数字个数，用于计算rank等属性
|
|
|
} tr[N];
|
|
|
|
|
|
int root, idx; //用于动态开点，配合tr记录FHQ Treap使用
|
|
|
int x, y, z; //本题用的三个临时顶点号
|
|
|
|
|
|
void pushup(int p) {
|
|
|
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1; //合并信息
|
|
|
}
|
|
|
|
|
|
int get_node(int key) { //创建一个新节点
|
|
|
tr[++idx].key = key; //创建一个新点，值为key
|
|
|
tr[idx].val = rand(); //随机一个堆中索引号
|
|
|
tr[idx].size = 1; //新点，所以小于等于它的个数为1个，只有自己
|
|
|
return idx; //返回点号
|
|
|
}
|
|
|
|
|
|
//将以p为根的平衡树进行分裂，小于等于key的都放到以x为根的子树中，大于key放到以y为根的子树中
|
|
|
void split(int p, int key, int &x, int &y) {
|
|
|
if (!p) { //当前节点为空
|
|
|
x = y = 0;
|
|
|
return;
|
|
|
}
|
|
|
if (tr[p].key <= key)
|
|
|
x = p, split(tr[p].r, key, tr[p].r, y); // x确定了，左边确定了，但右边未确定，需要继续递归探索
|
|
|
else
|
|
|
y = p, split(tr[p].l, key, x, tr[p].l); // y确定了，右边确定了，但左边未确定，需要继续递归探索
|
|
|
|
|
|
pushup(p); //更新统计信息
|
|
|
}
|
|
|
|
|
|
//将以x，y为根的两个子树合并成一棵树.要求x子树中所有key必须小于等于y子树中所有key
|
|
|
int merge(int x, int y) {
|
|
|
if (!x || !y) return x + y; //如果x或者y有一个是空了，那么返回另一个即可
|
|
|
|
|
|
int p; //根,返回值
|
|
|
if (tr[x].val > tr[y].val) { // x.key<y.key,并且, tr[x].val > tr[y].val, x在y的左上，此时理解为大根堆,y向x的右下角合并
|
|
|
p = x;
|
|
|
tr[x].r = merge(tr[x].r, y);
|
|
|
} else {
|
|
|
p = y;
|
|
|
tr[y].l = merge(x, tr[y].l); //复读机
|
|
|
}
|
|
|
|
|
|
pushup(p); //更新统计信息
|
|
|
return p;
|
|
|
}
|
|
|
|
|
|
void insert(int key) {
|
|
|
split(root, key, x, y); //按k分割
|
|
|
root = merge(merge(x, get_node(key)), y); //在x与key节点合并,再与key合并
|
|
|
}
|
|
|
|
|
|
void remove(int key) {
|
|
|
split(root, key, x, z);
|
|
|
split(x, key - 1, x, y);
|
|
|
// x<=key ,再分x <= key - 1,y就是=key的树
|
|
|
y = merge(tr[y].l, tr[y].r); //删除y点(根)
|
|
|
root = merge(merge(x, y), z); //合并x,y,z
|
|
|
}
|
|
|
|
|
|
int get_rank(int key) { //按值查排名
|
|
|
split(root, key - 1, x, y); //按key-1分割,x子树大小+1就是排名
|
|
|
int rnk = tr[x].size + 1; //储存x的大小+1
|
|
|
root = merge(x, y);
|
|
|
return rnk;
|
|
|
}
|
|
|
|
|
|
int get_key(int rnk) { //按排名查值
|
|
|
int p = root;
|
|
|
while (p) {
|
|
|
if (tr[tr[p].l].size + 1 == rnk)
|
|
|
break; //找到排名了
|
|
|
else if (tr[tr[p].l].size >= rnk)
|
|
|
p = tr[p].l; //当前size>=rank,去左子树
|
|
|
else {
|
|
|
//去右子树中找rank -= 左子树大小+1(根)的排名
|
|
|
rnk -= tr[tr[p].l].size + 1;
|
|
|
p = tr[p].r;
|
|
|
}
|
|
|
}
|
|
|
return tr[p].key;
|
|
|
}
|
|
|
|
|
|
//返回<key的最大数
|
|
|
int get_prev(int key) {
|
|
|
split(root, key - 1, x, y); //按key-1分,x最右节点就是前驱
|
|
|
int p = x;
|
|
|
while (tr[p].r) p = tr[p].r; //向右走
|
|
|
int res = tr[p].key;
|
|
|
root = merge(x, y);
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
//返回>key的最小数
|
|
|
int get_next(int key) {
|
|
|
split(root, key, x, y); //按key分y最左节点是后继
|
|
|
int p = y;
|
|
|
while (tr[p].l) p = tr[p].l;
|
|
|
int res = tr[p].key;
|
|
|
root = merge(x, y);
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
//创建FHQ Treap带哨兵的空树
|
|
|
void build() {
|
|
|
get_node(-INF), get_node(INF);
|
|
|
root = 1, tr[1].r = 2; //+inf > -inf,+inf在-inf右边
|
|
|
pushup(root); //更新root的size
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
//事实证明，套路很重要
|
|
|
build();
|
|
|
|
|
|
int q;
|
|
|
cin >> q;
|
|
|
while (q--) {
|
|
|
int op, x;
|
|
|
cin >> op >> x;
|
|
|
if (op == 1)
|
|
|
insert(x);
|
|
|
else if (op == 2)
|
|
|
remove(x);
|
|
|
else if (op == 3)
|
|
|
printf("%d\n", get_rank(x) - 1); //因为前面多了-INF哨兵,所以排名还需要减1
|
|
|
else if (op == 4)
|
|
|
printf("%d\n", get_key(x + 1)); //本来需要查询排名为x的，现在由于增加了一个左哨兵，就需要查询x+1位的
|
|
|
else if (op == 5)
|
|
|
printf("%d\n", get_prev(x));
|
|
|
else if (op == 6)
|
|
|
printf("%d\n", get_next(x));
|
|
|
}
|
|
|
return 0;
|
|
|
} |
