题目描述

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

“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≤105
−109≤x≤109
数据保证合法。

输入样例：

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

输出样例：

-10
6

主要考点

堆

姊妹题

模拟堆

C ++代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 100010;

int h[N], hsize;//h[N]为堆,hsize为堆中元素的个数
int sub[N], k;//sub[k]存储第k个插入数的下标,k表示是第几个插入的数
int inver_sub[N];//inver_sub[x]存储堆中下标为x的数是第几个插入的
int n;//询问个数

//交换下标标为u和v两个点的信息
void swap_heap(int u, int v){
    swap(inver_sub[u], inver_sub[v]);//交换对应下标插入的次序
    swap(sub[inver_sub[u]], sub[inver_sub[v]]);//交换对应的下标
    swap(h[u], h[v]);//交换堆中的对应的值
}

void down(int u){
    int t = u;
    if(2 * u <= hsize && h[t] > h[2 * u]) t = 2 * u;
    if(2 * u + 1 <= hsize && h[t] > h[2 * u + 1]) t = 2 * u + 1;
    if(t != u){
        swap_heap(t, u);
        down(t);
    }
}

void up(int u){
    while(u / 2 && h[u] < h[u / 2]){
        swap_heap(u, u / 2);
        u /= 2;
    }
}

//清除小标为u的点
void remove(int u){
    // h[u] = h[hsize --];
    swap_heap(u, hsize);
    hsize --;
    down(u), up(u);//只执行其中一个
}

//插入一个数x
void insert(int x){
    h[++ hsize] = x;
    sub[++ k] = hsize;
    inver_sub[hsize] = k;
    up(hsize);
}

void modify(int u, int x){
    h[u] = x;
    down(u), up(u);//只执行其中一个
}

int main(){
    cin >> n;
    while(n --){
        string str;
        cin >> str;
        if(str == "I"){
            int x;
            cin >> x;
            insert(x);
        }else if(str == "PM"){
            cout << h[1] << endl;
        }else if(str == "DM"){
            remove(1);
        }else if(str == "D"){
            int k;
            cin >> k;
            remove(sub[k]);
        }else {
            int k, x;
            cin >> k >> x;
            modify(sub[k], x);
        }
    }
    return 0;
}