难度：进阶。题目原型为洛谷 P1801 黑匣子。本题的考点是用对顶堆维护第 k 小元素：大根堆保存当前最小的 k 个元素，小根堆保存其余元素，查询时大根堆堆顶即答案。

目标

完成本题后，你应该能够：

• 用「大根堆 + 小根堆」的对顶堆结构维护动态集合的第 k 小；
• 解释为什么 big.top() 始终等于第 k 小元素；
• 处理 k 随查询递增（而非固定）的情况。

前置知识

• 11.1 堆与堆序性质；
• std::priority_queue 的大小根堆两种声明方式。

题目

读入 M、N。接下来 M 个整数是 ADD 序列，N 个整数是 u 序列（保证非降序）。模拟：

• 依次把 ADD 序列第 1..M 个元素插入集合；
• 每次执行到第 u[i] 个 ADD 后，查询当前已插入元素中第 i 小的元素并输出（共 N 次查询，i = 1..N）。

用对顶堆维护第 i 小，i 随查询递增。

输入格式

• 第一行两个整数 M、N；
• 第二行 M 个整数，表示 ADD 序列；
• 第三行 N 个整数，表示 u 序列。

输出格式

N 行，每行一个整数，表示每次查询的第 i 小元素。

数据范围

项目	范围
ADD 个数 M、查询次数 N	1 ≤ N ≤ M ≤ 2 × 10⁵
元素值	−2 × 10⁹ ≤ x ≤ 2 × 10⁹

样例

样例输入

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

样例输出

3
3
1
2

样例解释

• 插入第 1 个元素 3 后，第 1 小是 3；
• 插入第 2 个元素后集合 {3, 1}，第 2 小是 3；
• 插入第 6 个元素后集合 {-1000, -4, 1, 2, 3, 8}，第 3 小是 1；
• 仍只有 6 个元素（u[4] = 6），第 4 小是 2。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-11/exercise/E-11-12-black-box
pnpm lab:score -- labs/chapter-11/exercise/E-11-12-black-box

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 含负值、重复值、u 中有重复下标的查询都通过
• 能说清「插入时按什么规则放入 big / small，查询前如何调整 big 的大小」

思考题

1. 为什么 u 序列必须非降序？如果乱序还能直接套用本算法吗？
2. 每次查询的 k 从 i 变成 i+1 时，对顶堆的两个堆大小关系应如何变化？

题解

点击查看题解

思路

维护两个堆：

• big：大根堆，保存当前集合中最小的 i 个元素；
• small：小根堆，保存其余元素。

插入 x 时，若 big 为空或 x <= big.top() 则放入 big，否则放入 small。查询前，把 big 的大小调整到恰好 i：

• big 太大：把 big.top() 移到 small；
• big 太小：把 small.top() 移到 big。

此时 big.top() 就是第 i 小元素。

复杂度分析

• 每次插入 / 调整：O(log M)；
• 总时间复杂度：O((M + N) log M)；
• 空间复杂度：O(M)。