有旋Treap

#include<iostream>using namespace std;
/*本代码模拟的是小根堆*/
const int N = 5e5+1, INF = 0x3f3f3f3f;
struct node {int l, r, val, pos, siz, cnt;
//val：结点的值，pos：随机生成的优先级（尽量避免退化成单链），siz：以该点为根节点的子树大小，cnt：与val值相同的节点个数（搜索二叉树不允许有两个值相同的节点）
};
node tree[N];
int cnt, root; //编号、根节点
int n;void zig(int &x) { //右旋（为左子节点的右节点）；实质：在满足二叉搜索树的性质的基础上比较优先级int y = tree[x].l;tree[x].l = tree[y].r;//左子节点的右节点变为父节点x的左子节点（不明白画个图）tree[y].r = x;//左子节点的右节点变为父节点tree[y].siz = tree[x].siz;//左子节点继承子树节点数量tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + tree[x].cnt;//更新x = y;//替代（为什么形参里传得是地址）
}
void zag(int &x) { //左旋（为右子节点的左子节点）int y = tree[x].r;//同上tree[x].r = tree[y].l;tree[y].l = x;tree[y].siz = tree[x].siz;tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + tree[x].cnt;x = y;
}
void insert(int &x, int key) {//插入新节点if (!x) {//当前节点不存在x = ++cnt;tree[x].val = key;tree[x].pos = rand();tree[x].l = tree[x].r = 0;tree[x].cnt = tree[x].siz = 1;return ;}++tree[x].siz;//子树节点数量加一if (key == tree[x].val) {++tree[x].cnt;//相同值的数量加一return ;}if (key < tree[x].val) {//二叉搜索树的性质（下同）insert(tree[x].l, key);if (tree[x].pos > tree[tree[x].l].pos)zig(x);return ;}if (key > tree[x].val) {insert(tree[x].r, key);if (tree[x].pos > tree[tree[x].r].pos)zag(x);return ;}
}
void del(int &x, int key) {//删除值为key的旧节点if (tree[x].val == key) {//当前结点的值恰好为key，所以接下来就不必进行if (tree[x].cnt > 1) {//存在多个--tree[x].cnt;--tree[x].siz;return;}if (!tree[x].l || !tree[x].r)//没有子节点或类似于一条单链x = tree[x].l + tree[x].r;//相当于用子节点直接替代或变为叶子节点else {if (tree[tree[x].l].pos < tree[tree[x].r].pos){//因为x将要被删除（所以讨论儿子），所以为了保证满足堆的性质，所以要先使用左旋或右旋，在删除//模拟的是小根堆（根节点优先级小于子节点）zig(x);del(x, key);}else{zag(x);del(x, key);}}return;}--tree[x].siz;if (key < tree[x].val)//二叉搜索树的性质del(tree[x].l, key);elsedel(tree[x].r, key);
}
int getpre(int key) {//得到前驱（比key小的最大值）int x = root, pre = -INF;//pr：找到的上一个前驱while (x) {//直至找到叶子节点if (tree[x].val < key)//既然当前节点的值比key小，满足前提条件，说明我们要去它的右子树去寻找尽可能大的值（BST二叉搜索树的性质）pre = tree[x].val, x = tree[x].r;else//如果连前提条件都不满足，即当前节点的值不小于key，那么就要去左子树里去找了x = tree[x].l;}return pre;//返回值
}
int getnex(int key) {//得到后继（比key大的最小值）（类似于前驱）int x = root, nex = INF;while (x) {if (tree[x].val > key)nex = tree[x].val, x = tree[x].l;elsex = tree[x].r;}return nex;
}
int queryval(int k) {//查询排名所对应的值int x = root;while (x) {if (k > tree[tree[x].l].siz && k <= tree[tree[x].l].siz + tree[x].cnt)//排名在子树范围内return tree[x].val;if (k <= tree[tree[x].l].siz)//小于范围，找左子树x = tree[x].l;else {//大于范围，找右子树//通常来说，根节点与左子树被看作是一体的，与右子树区分开，//例如ls=1,2,3 x=5 rs=6,7，那么3在树和子树中都是第三个，而6在树中是第5名，在右子树中是第1名k -= tree[tree[x].l].siz + tree[x].cnt;x = tree[x].r;}}return 0;
}
int queryrank(int key) {//查询值所对应的排名int x = root, res = 0;while (x) {if (key == tree[x].val)//刚好相等return res + tree[tree[x].l].siz + 1;//从左子树的范围转移过来if (key < tree[x].val)//小于值（根据性质，去找左子树）x = tree[x].l;else {//大于值（根据性质，去找右子树）res += tree[tree[x].l].siz + tree[x].cnt;x = tree[x].r;}}return res;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;int op, x;for (int i = 1; i <= n; ++i) {cin >> op >> x;switch (op) {case 1:insert(root, x);break;case 2:del(root, x);break;case 3:cout << queryrank(x) << '\n';break;case 4:cout << queryval(x) << '\n';break;case 5:cout << getpre(x) << '\n';break;case 6:cout << getnex(x) << '\n';break;}}return 0;
}