题目描述您需要写一种数据结构来维护一些数都是绝对值 109 以内的数的集合最开始时集合是空的。其中需要提供以下操作操作次数 q 不超过 104定义数 x 的排名为集合中小于 x 的数的个数 1。查询数 x 的排名。注意 x 不一定在集合里。查询排名为 x(x≥1) 的数。保证集合里至少有 x 个数。求 x 的前驱前驱定义为小于 x且最大的数。若不存在则输出 −2147483647。求 x 的后继后继定义为大于 x且最小的数。若不存在则输出 2147483647。插入一个数 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; }