洛谷 P1801 黑匣子

// 第一反应：每来一次 GET，就把前 u[i] 个数**排一遍序**，取第 i 个
//
// 答案完全正确，而且好写。它的问题只有一个字：**慢**。
//   每次 GET 都排一遍 ⇒ O(nm log m)。
//   题面顶格 n = m = 2×10^5 ⇒ 想都别想。
//
// ★ 那它能不能靠题面那句「对于 30% 的数据，n, m ≤ 10^4」拿 30 分？——**不能**：
//   本机实测 m = n = 10^4 要 **3.73 秒**，而时限只有 **0.5 秒**（第 ② 步那张表）。
//   ⚠ 而只要把 sort 换成 nth_element，同一档就是 **0.27 秒** —— 那 30 分就到手了。
//   ⇒ **「去掉一个 log」在这道题上不是锦上添花，它正好压在 0 分和 30 分的分界线上。**

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> a(m + 1), u(n + 1);
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> u[i];

    string out;
    for (int i = 1; i <= n; i++) {
        vector<int> v(a.begin() + 1, a.begin() + 1 + u[i]);
        sort(v.begin(), v.end());                    // ⚠ 每次都从头排一遍
        out += to_string(v[i - 1]);
        out += '\n';
    }
    cout << out;
    return 0;
}

// P1801 黑匣子 —— ★ 这一版就能 AC：**对顶堆**（两个堆背靠背卡住第 k 小）
//
// ============ 一句话 ============
//   左边一个**大根堆** L：装着「到现在为止最小的 k 个」，堆顶是这 k 个里最大的那个
//                        —— 也就是**第 k 小**，`O(1)` 就能报出来；
//   右边一个**小根堆** R：装着剩下的全部，堆顶是「第 k+1 小」。
//   两个堆顶背靠背卡着一条缝，那条缝就是答案的位置。
//
// ============ 两个操作各干什么 ============
//   ADD(x)：x 该进哪边？—— 和 L 的堆顶比一下。
//           比它小 ⇒ x 挤进了「最小的 k 个」，那就把 L 的堆顶（原来的第 k 小）挤到 R 去；
//           否则 ⇒ 直接扔进 R。
//   GET   ：k 要 +1 ⇒ L 得长大一个 ⇒ 把 R 的堆顶（第 k+1 小）搬过来，然后输出 L 的堆顶。
//
//   ⇒ 每个元素一辈子只在两个堆之间挪常数次，总共 O((n + m) log m)。
//
// ★ 这就是[本章第 12 步](/ch/37-heap/)那招「大小为 k 的堆」的**在线版**：
//   那儿的 k 是固定的、数据是一趟流过；这儿的 k 每次 GET 都要长大一个,
//   所以光有 L 不够 —— **得有 R 帮它记住「下一个该轮到谁」**。
//
// ⚠ 题面 |aᵢ| ≤ 2×10⁹，而 int 的上限是 2 147 483 647 ⇒ **够，余量只有 7.4%**。
// ⚠ u 序列单调不降是**命门**（第 ⑤ 步量过）：它保证 ADD 只往前走，从不回头。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> a(m + 1), u(n + 1);
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> u[i];

    priority_queue<int> L;                                    // 大根堆：最小的 k 个
    priority_queue<int, vector<int>, greater<int>> R;         // 小根堆：其余的
    string out;

    int p = 1;                                                // 已经 ADD 到第 p−1 个
    for (int i = 1; i <= n; i++) {
        while (p <= u[i]) {                                   // ⚠ 必须是 while：同一个 u 可能来好几次 GET
            int x = a[p++];
            if (!L.empty() && x < L.top()) {                  // x 挤进了「最小的 k 个」
                R.push(L.top());
                L.pop();
                L.push(x);
            } else {
                R.push(x);
            }
        }
        L.push(R.top());                                      // k 长大一个：把第 k+1 小搬过来
        R.pop();
        out += to_string(L.top());                            // ★ 大根堆的堆顶就是第 k 小
        out += '\n';
    }
    cout << out;
    return 0;
}

// ✗ 错法一：把那句 while 写成了 if —— **一次 ADD 之后只处理一个 GET**
//
// 为什么会这么写：脑子里的模型是「一个 ADD 配一个 GET」，
// 而题面第 11 行那张表里 **第 9、10 两行是连着两个 GET**（u = [1, 2, 6, 6]，两个 6）。
//
// ⚠ 一旦 u 里出现相等的相邻项，这一版就少推进了 —— 它把「还没 ADD 够」的状态当成了 ADD 够了。
// ★ 官方样例正好考到了这件事（`1 2 6 6`），**一测就死**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> a(m + 1), u(n + 1);
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> u[i];

    priority_queue<int> L;
    priority_queue<int, vector<int>, greater<int>> R;
    string out;

    int p = 1;
    for (int i = 1; i <= n; i++) {
        if (p <= u[i]) {                             // ⚠ 这里本该是 while
            int x = a[p++];
            if (!L.empty() && x < L.top()) { R.push(L.top()); L.pop(); L.push(x); }
            else R.push(x);
        }
        if (R.empty()) { out += "?\n"; continue; }   // ★ 演示用的出口：不给它死循环 / 崩溃的机会
        L.push(R.top());
        R.pop();
        out += to_string(L.top());
        out += '\n';
    }
    cout << out;
    return 0;
}