形式化题目

给定长度为 $M$ 的序列 $A(1), A(2), \dots, A(M)$ 和长度为 $N$ 的序列 $u(1), u(2), \dots, u(N)$，满足 $1 \le N \le M \le 30000$、$|A(i)| \le 2 \times 10^9$，且对所有 $p$ 有 $p \le u(p) \le M$。

维护一个初始为空的整数多重集合和计数器 $i = 0$。序列 $A$ 依次给出所有 ADD(x) 操作的参数；第 $p$ 次 GET 操作发生在第 $u(p)$ 个元素加入之后，它使 $i$ 增加 $1$ 并输出当前集合升序后的第 $i$ 小。由于第 $p$ 次 GET 时盒内至少要有 $p$ 个数，$u$ 是单调不减的。

对每个 $p = 1, 2, \dots, N$，即求

样例推演

以 $A = (3, 1, -4, 2, 8, -1000, 2)$、$u = (1, 2, 6, 6)$ 为例，下表用正解的两个堆 （small 为存"当前最小的若干个数"的大根堆，加粗其堆顶；big 为其余数的小根堆） 展示每次 GET 前后的变化，具体机制见下文正解：

第 3 行最有代表性：一次 GET 前插入了 4 个元素，左侧攒到 6 个、超出 $p = 3$， 于是把左侧最大的 3 和 2 依次"还"给右侧；第 4 行 $p$ 变成 4 却没有新元素， 只需从右侧借一个最小值 2。答案始终是左侧的堆顶。

暴力解法

思路

按 $u$ 还原操作序列：从左到右扫描 $p = 1 \dots N$，先把 $A\big(u(p-1)+1 \dots u(p)\big)$ 依次加入集合，再对当前集合整体排序（或线性选择）取出第 $p$ 小输出。

这个做法正确且直观，但每次 GET 都对"几乎没变"的集合从头重算一次顺序统计量。

代码

暴力层省略代码：按本篇要求不单独提供暴力实现（无 brute 文件），朴素做法仅用于暴露瓶颈，思路见上文；正式解法见下方正解的代码。

复杂度

第 $p$ 次 GET 花费 $O\big(u(p)\log u(p)\big)$，总计 $O(NM \log M)$；即使用线性选择 也是 $O(NM)$。$M = 3 \times 10^4$ 时分别约为 $10^{10}$ 与 $9 \times 10^8$，都远超时限。

瓶颈

瓶颈在于每次询问都从头重算：相邻两次 GET 之间集合只新增了 $u(p) - u(p-1)$ 个元素，要输出的排名也只从 $p-1$ 走到 $p$——旧的第 $p-1$ 小 信息几乎可以全部复用，却被排序扔掉了。

正解

关键观察

1. 要维护的排名恰好是 $1, 2, 3, \dots$ 递增：第 $p$ 次 GET 要第 $p$ 小， 不是任意排名。因此"最小的一些数"这个前缀每轮只会多要一个，维护它的代价 可以摊还很小的常数。
2. 集合只增不减：插入后第 $p$ 小只可能不变或变大，所以围绕 “当前最小的 $p$ 个数” 做增量维护是安全的。

把集合沿全局排序切成两段，用一个数据结构各管一段，让左段的大小恒等于 $p$， 答案就是左段的最大值。

思路

维护对顶堆：

• 大根堆 small：始终保持"恰好是当前集合中最小的 len(small) 个数"， 堆顶即当前第 len(small) 小；
• 小根堆 big：装剩下的所有数。两堆合起来是全集。

处理第 $p$ 次 GET 分三步：

1. 补齐插入：把 $A\big(u(p-1)+1 \dots u(p)\big)$ 依次插入。每个新元素 $x$ 与左侧堆顶比较：$x$ 比左侧最大值还小就进 small，否则进 big。 这个贪心保证 small 始终装着"最小的一段数"。
2. 左借：若 len(small) < p，从 big 弹出最小值压入 small。
3. 右还：若 len(small) > p，把 small 的堆顶（左侧最大）弹回 big。

平衡后 len(small) == p，堆顶就是第 $p$ 小。注意插入和平衡的先后次序： 先全部插入、再借/还，借还只沿"全局排序的左右边界"滑动元素，不破坏 "small 是最小的一段"这一性质。

flowchart LR
    A["第 p 次 GET：补齐插入<br/>新元素 x 与左堆顶比较<br/>x 更小进 small，否则进 big"] --> B{"len(small) 与 p 的关系"}
    B -->|"不足 p"| C["左借：big 弹最小值<br/>压入 small"]
    B -->|"超过 p"| D["右还：small 弹最大值<br/>还给 big"]
    B -->|"恰为 p"| E
    C --> E["输出 -small 堆顶<br/>即当前第 p 小"]
    D --> E

实现上，Python 的 heapq 只有最小堆，所以 small 用相反数存储： 比较写 x < -small[0]，输出时再取负号翻回来。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 12:50
# update_at: 2026-10-01 12:47

import sys
from heapq import heappop, heappush


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)
    a = [next(data) for _ in range(m)]  # 按加入顺序排列的元素
    u = [next(data) for _ in range(n)]  # u[k]：第 k 次 GET 时盒内元素个数

    small: list[int] = []  # 存相反数的大根堆：始终恰好是"当前最小的 len(small) 个数"
    big: list[int] = []    # 小根堆：剩下的数
    out: list[str] = []
    added = 0  # 已经入盒的元素个数

    for k, need in enumerate(u, 1):
        while added < need:  # 补齐到第 k 次 GET 时的盒内元素个数
            x = a[added]
            added += 1
            if small and x < -small[0]:
                heappush(small, -x)  # x 比"已有最小数"的最大值还小，归入左侧
            else:
                heappush(big, x)
        while len(small) < k:            # 左侧不足 k 个：从右侧借最小的
            heappush(small, -heappop(big))
        while len(small) > k:            # 左侧超过 k 个：把最大的还回右侧
            heappush(big, -heappop(small))
        out.append(str(-small[0]))       # 左侧最大值就是第 k 小

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:52
 * update_at: 2026-10-06 16:52
 */

// 对顶堆求第 p 小：大根堆 small 维护"当前最小的 p 个数"，堆顶即答案；
// 小根堆 big 装剩下的数，两堆合起来是全集。
// 注意 |A(i)| <= 2*10^9 超出 int 范围，题目数据用 ll。
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

typedef long long ll;

const ll MAXM = 30005;

ll m, n;
ll a[MAXM]; // a[i] = 序列 A 的第 i 个加入元素（下标从 1 开始）
ll u[MAXM]; // u[p] = 第 p 次 GET 时盒内元素个数（下标从 1 开始）

priority_queue<ll> small; // 大根堆：装当前最小的若干个数，堆顶是第 p 小
priority_queue<ll, vector<ll>, greater<ll> > big; // 小根堆：装其余的数

// 读取输入
void read_input() {
    scanf("%lld %lld", &m, &n);
    for (ll i = 1; i <= m; i++) scanf("%lld", &a[i]);
    for (ll p = 1; p <= n; p++) scanf("%lld", &u[p]);
}

// 依次处理 N 次 GET
void solve() {
    ll p = 1; // 第 p 次 GET，small 的目标大小就是 p
    for (ll i = 1; i <= m; i++) {
        ll x = a[i];
        // 贪心：比左侧最大值还小的数进 small，否则进 big，保证 small 是最小的一段
        if (small.empty() || x < small.top())
            small.push(x);
        else
            big.push(x);

        // u[p] == i 说明第 p 个元素已加入，第 p 次 GET 发生在此刻之后
        while (p <= n && u[p] == i) {
            // 左借：small 不足 p 个，从 big 借最小值
            while ((ll)small.size() < p) {
                small.push(big.top());
                big.pop();
            }
            // 右还：small 超过 p 个，把左侧最大值还给 big
            while ((ll)small.size() > p) {
                big.push(small.top());
                small.pop();
            }
            printf("%lld\n", small.top()); // 堆顶即当前第 p 小
            p++;
        }
    }
}

int main() {
    read_input();
    solve();
    return 0;
}

复杂度

• 时间 $O(M \log M)$：每个元素最多进出 small 常数次（len(small) 随 $p$ 单调加 1、超过时还回，摊还每个元素进出左堆的次数是常数），每次堆操作 $O(\log M)$。$M = 3 \times 10^4$ 时约 $4.5 \times 10^5$ 次堆操作，远优于暴力。
• 空间 $O(M)$：两堆合计存放全部元素。

总结

• 本题的关键是把"每次询问重算第 $p$ 小"改成把答案物化成数据结构的状态： 对顶堆的左堆大小恒等于当前询问的排名，堆顶即答案。
• 排名恰好 $1, 2, \dots$ 递增 + 集合只增不减，是左堆只需"借/还"平衡、 每轮摊还 $O(1)$ 次移动的前提；如果询问的是任意排名，就要换成权值 树状数组或平衡树。
• 对顶堆是"动态第 $k$ 小（$k$ 单调变化）"这一类问题的标准套路，也常见于 "数据流的中位数"等变体。