..
AcWing 106. 动态中位数
本题有两种做法，使用 “对顶堆” 的在线做法（读入的同时即时计算答案）和利用 “链表+Hash” 的离线做法（完成所有读入后进行计算再统一输出）。
为了动态维护中位数，我们可以建立两个二叉堆：一个小根堆，一个大根堆。
在依次读入这个整数序列的过程中，设当前序列长度为 $M$，我们始终保持：
- 序列中从小到大排名为 $1 \sim M / 2$ 的整数存储在大根堆中；
- 序列中从小到大排名为 $M / 2 + 1 \sim M$ 的整数存储在小根堆中。
任何时候，如果某一个堆中元素个数过多，打破了这个性质，就取出该堆的堆顶插入另一个堆。
这样一来，序列中的中位数就是小根堆堆对顶。
每次新读入一个数值 $X$ 后，若 $X$ 比 中位数小，则插入大根堆，否则插入小根堆，在插入后检查并维护上述性质即可。
这就是 “对顶堆” 算法。
完整代码：动态中位数.cpp