摘要：
题目 维护一个集合，初始时集合为空，支持如下几种操作：
$I \quad x$，插入一个数 $x$；
$PM$，输出当前集合中的最小值；
$DM$，删除当前集合中的最小值（数据保证此时的最小值唯一）；
$D \quad k$，删除第 $k$ 个插入的数；
$C \quad k \quad x$，修改第 $k$ 个插入的数，将其变为 $x$；
输入格式
接下来 $N$ 行，每行包含一个操作指令，操作指令为 $I \quad x$, $PM$, $DM$, $Dk$ 或 $C \quad k \quad x$ 中的一种。
输入格式
每个结果占一行。
数据范围
$1≤N≤10^5$
$−10^9≤x≤10^9$
数据保证合法。
输入样例：
8
输出样例：
-10
代码 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 #include <bits/stdc++.h> using namespace std ;const int N = 1000010 ;int h[N], ph[N], hp[N];int n, idx;void heap_swap (int u, int i) int k1 = hp[u]; int k2 = hp[i]; ph[k1] = i; ph[k2] = u; hp[u] = k2; hp[i] = k1; swap(h[u], h[i]); } void heap_swap_1 (int a, int b) swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down (int i) int u = i; if (i * 2 <= idx && h[i * 2 ] < h[i]) u = i * 2 ; if (i * 2 + 1 <= idx && h[i * 2 + 1 ] < h[u]) u = i * 2 + 1 ; if (u != i) { heap_swap(u, i); down(u); } } void up (int i) for (; i >> 1 && h[i >> 1 ] > h[i];) { heap_swap(i, i >> 1 ); i >>= 1 ; } } int main () cin >> n; for (; n--;) { string ops; cin >> ops; int k, x; if (ops == "I" ) { static int insert_cnt = 0 ; ++insert_cnt; cin >> x; h[++idx] = x; ph[insert_cnt] = idx; hp[idx] = insert_cnt; up(idx); } else if (ops == "PM" ) { cout << h[1 ] << endl ; } else if (ops == "DM" ) { heap_swap(1 , idx); --idx; down(1 ); } else if (ops == "D" ) { cin >> k; int k_idx = ph[k]; heap_swap(k_idx, idx); --idx; up(k_idx); down(k_idx); } else if (ops == "C" ) { cin >> k >> x; int k_idx = ph[k]; h[k_idx] = x; up(k_idx); down(k_idx); } } }
理解 数组模拟堆，建堆逻辑见这篇文章：AcWing 838. 堆排序
相比较，本题额外需要支持删除和修改第k个插入的数。那么我们需要维护一个数据结构可以对应找到第 $k$ 个插入的数在堆数组中的位置。
我们用 $ph$ 数组维护该映射关系，int u = ph[k] 表示第 $k$ 个插入的数在堆数组 $h$ 中的下标为 $u$。
仔细思考不难发现，当我们交换堆数组中两个元素数值的位置时，如果用传统的 $swap$ 方法交换数组数值位置，会打乱第 $k$ 个插入数在下标K和堆数组数值下标的映射关系。所以交换时我们也必须要同时交换这个映射关系。
继续思考容易想到，在我们交换两个数插入次序和值下标映射关系时，需要知道两个值下标对应的 $k$ 是多少，因为我们交换函数的入参只有两个值在堆数组中的下标。那么我们需要维护一个数据结构可以根据堆数组数值下标找到其插入次序。
我们用 $hp$ 数组维护该映射关系，int k = hp[u] 表示堆数组下标为 $u$ 的数是第 $k$ 次插入的。
重构交换函数，逻辑是：
先根据两个值在堆数组中的下标找到两个数分别是第几次插入的（用到未交换次序的 $hp$ 数组），再根据两者的插入次序交换其对应在堆数组中的下标，完成第一次 $ph$ 映射交换；
接着根据两个值在数组中的下标交换其对应的插入次序，完成第二次 $hp$ 映射交换；
进行堆数组数值交换。