题目描述

要求维护一个集合，满足插入元素、输出最小元素、删除最小元素、删除第k个插入的元素、修改第k个插入元素的值，这五个操作；

样例

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

-10
6

算法1

堆+集合映射

这个题中很明显五个操作都是堆的经典操作，但是将任意元素改成了第k个插入的元素，又因为存放堆的数组是一个下标和值会动态变化的数组，所以我们需要增加两个相互映射的数组；
1. 一个数组ph[]是 第k个插入的元素和其在堆里的下标之间的映射，用于找到第k个插入元素在堆中的位置；
2. 另一个数组hp[]是 堆中元素到其插入顺序的映射，用于在更新ph[]数组时能快速定位；

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+7;
int heap[N], hp[N], ph[N], sz;
//heap[]是堆数组，hp[]记录堆中元素到插入顺序的映射，ph[]记录插入顺序到堆中元素的映射，sz为堆大小；

void heap_swap(int a, int b){
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    //这三个语句可以任意调换位置，因为位置相互对应，所以谁先调换都是是等价的；
}

void down(int k){
    int t = k;
    if(2*k <= sz && heap[2*k] < heap[t]) t = 2*k;
    if(2*k+1 <= sz && heap[2*k+1] < heap[t]) t = 2*k+1;
    if(t != k){
        heap_swap(t, k);
        down(t);
    }
}

void up(int k){
    if(k/2 > 0 && heap[k] < heap[k/2]){
        heap_swap(k, k/2);
        up(k/2);
    }
}

int main()
{
    ios::sync_with_stdio(false);

    int n, k, x, num = 0;   //num用来记录插入次数；
    cin>>n;
    string op;
    while(n--){
        cin>>op;
        if(op == "I"){      //插入操作需要将ph[]数组与hp[]数组新建一个对应关系；
            cin>>x;
            heap[++sz] = x;
            ph[++num] = sz;
            hp[sz] = num;
            up(sz);
        }
        else if(op == "PM")
            cout<<heap[1]<<endl;
        else if(op == "DM"){
            heap_swap(1, sz--);
            down(1);
        }
        else if(op == "D"){
            cin>>k;
            int u = ph[k];  //这里需要记录ph[k]的原因是heap_swap会更改ph[k]的值；
            heap_swap(u, sz--);
            up(u);
            down(u);
        }
        else{
            cin>>k>>x;
            heap[ph[k]] = x;
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}