洛谷 P3378 【模板】堆

// P3378【模板】堆 —— ★ 这一版就能 AC（手写小根堆，正文第 5、6 步原样搬过来）
//
// 和正文那道题的差别只有两处，**都不在算法上**：
//   ① 没有「最后一行把剩下的倒出来」那一问（正文是自己加的，为的是让 bug 露头）；
//   ② 规模从 2×10⁵ 涨到 **10⁶**，而时限只有 1 秒 ⇒ 读入那笔账要算（第 ⑥ 步）。
//
// ⚠ 题面写的是 `1 ≤ x < 2^31` —— **恰好是 int 的正数半边，一个值都不剩**：
//   int 的上限 2147483647 就是 2^31 − 1，所以 int 够用，**余量为 0**。
//   ⇒ 任何「拿一个大常数当哨兵」的写法在这道题上都是错的（第 ④ 步 p3378Inf.cpp）。

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

const int MAXN = 1000006;
int a[MAXN];                                   // ★ a[1..sz] 才是堆，a[0] 空着不用
int sz = 0;

/** 上浮：比爸爸小就往上（空穴法，每层只有一次赋值） */
void up(int i) {
    int x = a[i];
    while (i > 1 && a[i >> 1] > x) { a[i] = a[i >> 1]; i >>= 1; }
    a[i] = x;
}

/** 下沉：两个儿子里挑**小**的那个换 */
void down(int i) {
    int x = a[i];
    while ((i << 1) <= sz) {
        int c = i << 1;
        if (c < sz && a[c + 1] < a[c]) c++;    // ⚠ c < sz 才有右儿子
        if (a[c] >= x) break;
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}

int main() {
    ios::sync_with_stdio(false);               // ★ 第 ⑥ 步量过：这一句在这道题上值 3.4 倍
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    string out;
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            a[++sz] = x;
            up(sz);
        } else if (op == 2) {
            out += to_string(a[1]);            // 堆顶就是最小值，O(1)
            out += '\n';
        } else {
            a[1] = a[sz--];                    // 拿最后一格填到根上，再沉下去
            if (sz) down(1);
        }
    }
    cout << out;
    return 0;
}

// ✗ 第一反应：「不就是求最小吗，用一个变量记着就行了」
//
// 插入时 mn = min(mn, x)，查询就输出 mn —— 前两问都对。
// ⚠ 到第三个操作（删除最小）就露馅了：**删掉之后 mn 该变成谁？这一版答不上来。**
//   （它只能把 mn 重新设回 INF，于是后面的查询全错。）
//
// ★★ 这一版存在的意义是把这道题真正的难点摆出来：
//   难的不是「求最小」，是「**删掉最小之后还要能接着求最小**」——
//   一个变量记不住第二小是谁，而重新扫一遍就是 O(n)。
//
// ⚠ 顺带演示题面那句 `x < 2^31` 的分量：这里的 INF 写的是 0x3f3f3f3f = 1 061 109 567，
//   它**比一半以上的合法 x 还小**（第 ④ 步细说）。

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

const int INF = 0x3f3f3f3f;

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

    int n;
    if (!(cin >> n)) return 0;

    int mn = INF;
    string out;
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) { int x; cin >> x; mn = min(mn, x); }
        else if (op == 2) { out += to_string(mn); out += '\n'; }
        else mn = INF;                         // ⚠ 删掉之后只能认输
    }
    cout << out;
    return 0;
}