知识点：建堆 + 扩展
维护一个集合，初始时集合为空，支持如下几种操作：
- “I x”，插入一个数x；
- “PM”，输出当前集合中的最小值；
- “DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
- “D k”，删除第k个插入的数；
- “C k x”，修改第k个插入的数，将其变为x；
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。
输入格式
第一行包含整数N。
接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。
输出格式
对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
//建堆
//删除最小值
//删除指定下标k
//插入
//修改k的值import java.io.*;
import java.lang.Integer;class Main{static int N = 100010;static int[] t = new int[N];//堆static int[] ph = new int[N];//指针到堆static int[] hp = new int[N];//堆到指针static int size = 0;public static void swap(int a ,int b){int temp=t[a];t[a] = t[b];t[b] = temp;temp = ph[hp[a]];ph[hp[a]] = ph[hp[b]];ph[hp[b]] = temp;temp = hp[a];hp[a] = hp[b];hp[b] = temp;}static void down(int n){//向下更新int x = n;if(n * 2 <= size && t[x] > t[n * 2])x = n * 2;if(n * 2 + 1 <= size && t[x] > t[n * 2 + 1])x = n * 2 + 1;if(n != x){swap(n, x);down(x);}}static void up(int n){//向上更新while(n / 2 != 0 && t[n / 2] > t[n]){swap(n / 2, n);n /= 2;}}public static void main(String[] args)throws Exception{BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter buw = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.valueOf(buf.readLine());size = 0;int c = 0;for(int i = 1; i <= n; ++i){String[] params = buf.readLine().split(" ");if("I".equals(params[0])){c++;size++;t[size] = Integer.valueOf(params[1]);ph[c] = size;hp[size] = c;up(size);}else if("PM".equals(params[0])){buw.write(t[1] + "\n");}else if("DM".equals(params[0])){swap(1, size);size--;down(1);}else if("D".equals(params[0])){int k = Integer.valueOf(params[1]);k = ph[k];swap(k, size);size--;down(k);up(k);}else{int k = Integer.valueOf(params[1]);int v = Integer.valueOf(params[2]);t[ph[k]] = v;down(ph[k]);up(ph[k]);}}buw.flush();buf.close();buw.close();}
}