维护一个集合，初始时集合为空，支持如下几种操作：

1. “I x”，插入一个数x；
2. “PM”，输出当前集合中的最小值；
3. “DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. “D k”，删除第k个插入的数；
5. “C k x”，修改第k个插入的数，将其变为x；

现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式

第一行包含整数N。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。

输出格式

对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤105
−109≤x≤109
数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

Go 代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

var (
    h    []int
    ph   []int
    hp   []int
    size int
)

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
    new(os.Stdin)

    x := readLine()
    var m int
    n, _ := strconv.Atoi(x[0])
    h = make([]int, n+2)  // h[N] 存储堆中的值
    ph = make([]int, n+2) // ph[k] 存储第k个插入的点在堆中的位置
    hp = make([]int, n+2) // hp[k] 存储堆中下标是 k 的点是第几个插入的

    for i := 0; i < n; i++ {
        x = readLine()
        switch x[0] {
        case "I": // 插入一个数 v
            v, _ := strconv.Atoi(x[1]) // 读入需要插入的数
            size++
            m++
            ph[m] = size
            hp[size] = m
            h[size] = v
            up(size)
        case "PM": // 输出当前集合中的最小值
            fmt.Println(h[1])
        case "DM": // 删除当前集合中的最小值（数据保证此时的最小值唯一）
            swap(1, size)
            size--
            down(1)
        case "D": // 删除第k个插入的数
            k, _ := strconv.Atoi(x[1]) // 读入删除第k个插入的数
            k = ph[k]
            swap(k, size)
            size--
            down(k) // down 和 up 只会运行一个
            up(k)
        case "C": // 修改第 k 个插入的数，将其变为 v
            k, _ := strconv.Atoi(x[1]) // 读入修改第 k 个插入的数
            v, _ := strconv.Atoi(x[2]) // 读入修改为 v
            k = ph[k]
            h[k] = v
            down(k)
            up(k)
        }
    }
}

// 交换两个点，及其映射关系
func swap(a, b int) {
    ph[hp[a]], ph[hp[b]] = ph[hp[b]], ph[hp[a]]
    hp[a], hp[b] = hp[b], hp[a]
    h[a], h[b] = h[b], h[a]
}

// 往下调整
func down(u int) {
    t := u                            // t 表示三个点的最小值
    if u*2 <= size && h[u*2] < h[t] { // 左儿子存在并且左儿子的值小于h[t]
        t = u * 2 // t就等于左儿子
    }
    if u*2+1 <= size && h[u*2+1] < h[t] {
        t = u*2 + 1 // t就等于右儿子
    }
    if u != t { // 根节点不是最小值
        swap(u, t)
        down(t)
    }
}

// 往上调整
func up(u int) {
    for u/2 > 0 && h[u/2] > h[u] { // 存在父节点，并且父节点大于当前节点
        swap(u/2, u) // 不平衡，进行交换
        u /= 2
    }
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}
func readLine() []string {
    scanner.Scan()
    return strings.Split(scanner.Text(), " ")
}