题目分析

利用堆的特性，使用upadjust与downadjust进行调整
注意删除第K个插入元素还需要向上进行调整，因为无法确定第k个插入元素与堆的最后一个元素的大小关系（实际上只有当第k个插入元素在堆中的位置处在堆的最后一个元素的祖先位置时才可以确定他们的大小关系）

相关代码实现

//特别要注意删除第 k 个插入的数时 还需要向上进行调整

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int heap[N];
int pn[N]; //存储第k个插入的点在堆中的位置
int hp[N]; //存储堆中下标是k的点是第几个插入的

void swap_heap(int i,int j){
     swap(pn[hp[i]],pn[hp[j]]);
     swap(hp[i],hp[j]);
     swap(heap[i],heap[j]);
}

void downadjust(int left,int right){
    int i=left;
    int j=i*2;
    while(j<=right){
        if(j+1<=right&&heap[j+1]<heap[j]) j=j+1;

        if(heap[j]<heap[i]){
            swap_heap(i,j);
            i=j;
            j=i*2;
        }

        else 
            break;
    }
}

void upadjust(int left,int right){
    int i=right;
    int j=i/2;
    while(j>=left){
        if(heap[j]>heap[i]){
            swap_heap(i,j);
            i=j;
            j=i/2;
        }

        else 
            break;
    }
}

int main(){
    int n;
    cin>>n;

    int ppos=1; //区分堆的大小与插入次数
    int len=0;

    for(int i=1;i<=n;i++){
        string str;
        cin>>str;

        if(str=="I"){
            int x;
            cin>>x;
            len++;
            heap[len]=x;
            pn[ppos]=len;
            hp[len]=ppos;
            upadjust(1,len);
            ppos++;

            int pos=pn[ppos-1];
            //cout<<x<<" heap[pos]:"<<heap[pos]<<endl;
            //cout<<len<<" pos:"<<pos<<endl;
        }

        if(str=="PM"){
            cout<<heap[1]<<endl;
        }

        if(str=="DM"){
            swap_heap(1,len);
            len--;
            downadjust(1,len);
        }

        if(str=="D"){
            int k;
            cin>>k;
            int pos=pn[k]; //无法确定heap[pos]与heap[len]的大小关系(除非heap[pos]是heap[len]的祖先)
            swap_heap(pos,len);
            len--;
            upadjust(1,pos);  //关键所在 不可缺少
            downadjust(pos,len);
        }

        if(str=="C"){
            int k,x;
            cin>>k>>x;
            int pos=pn[k];

            heap[pos]=x;
            upadjust(1,pos);
            downadjust(pos,len);

        }
    }
    return 0;
}