洛谷P5076 【深基16.例7】普通二叉树（简化版）

题目描述

您需要写一种数据结构，来维护一些数（都是绝对值 109 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 q 不超过 104：

1. 定义数 x 的排名为集合中小于 x 的数的个数 +1。查询数 x 的排名。注意 x 不一定在集合里。
2. 查询排名为 x(x≥1) 的数。保证集合里至少有 x 个数。
3. 求 x 的前驱（前驱定义为小于 x，且最大的数）。若不存在则输出 −2147483647。
4. 求 x 的后继（后继定义为大于 x，且最小的数）。若不存在则输出 2147483647。
5. 插入一个数 x，本题的数据保证插入前 x 不在集合中。

保证执行 1,3,4 操作时，集合中有至少一个元素。

输入格式

第一行是一个整数 q，表示操作次数。

接下来 q 行，每行两个整数 op,x，分别表示操作序号以及操作的参数 x。

输出格式

输出有若干行。对于操作 1,2,3,4，输出一个整数，表示该操作的结果。

输入输出样例

输入

7 5 1 5 3 5 5 1 3 2 2 3 3 4 3

输出

2 3 1 5

#include <bits/stdc++.h> using namespace std; // Treap 节点结构 struct Node { int val; // 节点值 int pri; // 随机优先级 int size; // 子树大小 Node *left, *right; Node(int v) : val(v), pri(rand()), size(1), left(nullptr), right(nullptr) {} }; // 获取子树大小，处理空指针 int getSize(Node *p) { return p ? p->size : 0; } // 更新节点 size void update(Node *p) { if (p) { p->size = 1 + getSize(p->left) + getSize(p->right); } } // 右旋 void rotateR(Node* &p) { Node *q = p->left; p->left = q->right; q->right = p; update(p); update(q); p = q; } // 左旋 void rotateL(Node* &p) { Node *q = p->right; p->right = q->left; q->left = p; update(p); update(q); p = q; } // 插入节点（递归） void insert(Node* &p, int x) { if (!p) { p = new Node(x); return; } if (x < p->val) { insert(p->left, x); if (p->left->pri < p->pri) rotateR(p); // 维护堆性质 } else { insert(p->right, x); if (p->right->pri < p->pri) rotateL(p); } update(p); } // 查询 x 的排名（小于 x 的个数 + 1） int getRank(Node *p, int x) { if (!p) return 1; // 空树返回1（实际不会发生，但递归边界） if (x <= p->val) return getRank(p->left, x); else return getSize(p->left) + 1 + getRank(p->right, x); } // 查询排名为 k 的数（第 k 小） int kth(Node *p, int k) { int leftSize = getSize(p->left); if (k <= leftSize) return kth(p->left, k); else if (k == leftSize + 1) return p->val; else return kth(p->right, k - leftSize - 1); } // 求 x 的前驱（小于 x 的最大数） int predecessor(Node *p, int x) { if (!p) return -2147483647; if (p->val >= x) return predecessor(p->left, x); else { int rightRes = predecessor(p->right, x); if (rightRes == -2147483647) return p->val; else return rightRes; } } // 求 x 的后继（大于 x 的最小数） int successor(Node *p, int x) { if (!p) return 2147483647; if (p->val <= x) return successor(p->right, x); else { int leftRes = successor(p->left, x); if (leftRes == 2147483647) return p->val; else return leftRes; } } int main() { srand(time(0)); // 初始化随机种子 int q; cin >> q; Node *root = nullptr; // 根节点初始化为空 while (q--) { int op, x; cin >> op >> x; switch (op) { case 1: // 查询排名 cout << getRank(root, x) << endl; break; case 2: // 查询第 k 小的数 cout << kth(root, x) << endl; break; case 3: // 前驱 cout << predecessor(root, x) << endl; break; case 4: // 后继 cout << successor(root, x) << endl; break; case 5: // 插入 insert(root, x); break; default: break; } } return 0; }