前置节点：

贪心

STL

动态第 k 小

有一个序列初始为空，每次加入一个数次，求加入之后序列的第 $k$ 小， $k$ 会 $O(1)$ 地变化。

利用对顶堆的思想，开两个堆，一个大根堆 $q_1$，一个小根堆 $q_0$，$q_1$ 中的所有数字都比 $q_0$ 中的小。

当新加入一个数字时，优先插入 $q_0$ 中。

如果 $q_0$ 中的数字大于 $k$ ，则将 $q_0$ 的最小值（堆首）插入 $q_1$ ，反之则将 $q_1$ 的最大值插入 $q_0$。

此时第 $k$ 小值一定在两个堆的堆顶。

P1801 黑匣子

P1168 中位数