在放代码之前，先介绍一个库—— pbds（Policy-Based Data Structures），这是一个 GNU C++ STL 的扩展库，提供了增强版数据结构，包括优先队列，平衡树。 在 pbds 库中，有一个容器，叫 tree，是一种平衡二叉搜索树，可以支持按排名访问元素。 TREE 容器 定义 使用前提 * 需要包含<ext/pb_ds/assoc_container.hpp>，<ext/pb_ds/tree_policy.hpp> 头文件（注意，万能头文件中一般不含这两个头文件）。 * 使用 find_by_order 或 order_of_key 函数时，必须使用 tree_order_statistics_node_update 策略。 * 默认去重，重复元素需用 pair<value,unique number> 处理。 核心功能/函数 功能 函数 说明 返回值/类型 时间复杂度 * 插入元素 insert(x) 插入元素 x（唯一） void O(log n) 删除元素 erase(x) 删除值等于 x 的元素 void O(log n) 查找元素 find(x) 返回迭代器 iterator O(log n) 查找第 k 小 find_by_order(k) 返回第 k 小元素，0-index iterator O(log n) 查询排名 order_of_key(x) 返回严格小于 x 的元素数量 int O(log n) 大小 size() 当前元素个数 int O(1) 是否为空 empty() 检查是否为空 bool O(1) 清空 clear() 删除所有元素 void O(n) *：时间复杂度是在 rb_tree_tag 的基础上计算的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 『题解』A21561中位数 题目大意 题目等价于：动态维护前i个元素的有序序列，快速取第k小元素。 * 中位数的下标 k=i2\displaystyle k=\frac{i}{2}k=2i (1-indexed)。 * 输入 N≤105N \le 1 0^{5}N≤105，元素范围 0≤Ai≤1090 \le A_{i}\le 1 0^{9}0≤Ai ≤109。 代码实现 时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)O(nlogn)。

使用两个堆，大根堆维护较小的值，小根堆维护较大的值 即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的 将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆 那么就保证了所有大根堆中的元素都小于小根堆中的元素 于是我们发现对于大根堆的堆顶元素，有【小根堆的元素个数】个元素比该元素大，【大根堆的元素个数-1】个元素比该元素小； 同理，对于小跟堆的堆顶元素，有【大根堆的元素个数】个元素比该元素小，【小根堆的元素个数-1】个元素比该元素大； 那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后，元素个数较多的堆的堆顶元素即为当前中位数；（如果元素个数相同，那么就是两个堆堆顶元素的平均数，本题不会出现这种情况） 根据这两个堆的定义，维护方式也很简单，把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可 好了，下面上代码

创建一个大根堆（记录前半段）一个小根堆（记录后半段）