839. Simulation reactor

subject

Maintain a collection , Initially, the set is empty , The following operations are supported ：

I x, Insert a number x;
PM, Output the minimum value in the current set ;
DM, Delete the minimum value in the current set （ The data guarantees that the minimum value at this time is unique ）;
D k, Delete the first k The number of inserts ;
C k x, Amendment No k The number of inserts , Turn it into x;
Now it's time to N operations , For all the third 2 Operations , Output the minimum value of the current set .

Input format
The first line contains integers N.

Next N That's ok , Each line contains an operation instruction , The operation instruction is I x,PM,DM,D k or C k x One of the .

Output format
For each output instruction PM, Output a result , Represents the minimum value in the current set .

Each result takes up one line .

Data range
1≤N≤105
−109≤x≤109
The data is guaranteed to be legal .

sample input ：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
sample output ：
-10
6

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N], cnt;
int hp[N], ph[N];

void exchange(int a, int b)
{
    
    swap(ph[hp[a]], ph[hp[b]]);// The current location of the swap storage heap node , That is, update a The new location of the node and b The new location of the node 
    swap(hp[a], hp[b]);// In exchange for a Node on ph The value of the index in the array , Follow b Nodes in the ph The value of the index in the array 
    swap(h[a], h[b]);// The values of the two nodes of the swap heap 
}

void down(int u)
{
    
    int t = u;
    if(2*u <= cnt && h[2*u] < h[t]) t = 2*u;
    if(2*u+1 <= cnt && h[2*u+1] < h[t]) t = 2*u+1;
    if(t != u)// If you need to switch down 
    {
    
        exchange(t, u);// The smaller of the parent node and the two child nodes in the swap heap 
        down(t);// Continue to swap the smaller of the three values in the heap 
    }
}

void up(int u)
{
    
    while(u/2 && h[u] < h[u/2])// If u The parent node of the node exists , also u The value of the node <u/2 The value of the node 
    {
    
        exchange(u, u/2);// In the swap heap u and u/2 The nodes of the location 
        u/=2;// Continue to judge the parent node 
    }
}


int main()
{
    
    int n;
    cin >> n;
    
    int m = 0;
    
    while (n -- )
    {
    
        char op[5];
        int k, x;
        cin >> op;
        
        
        if(!strcmp(op,"I"))// If you need to insert a new heap node 
        {
    
            cin >> x;
            cnt++;// Number of heap nodes 
            m ++ ;// Number of inserts , As index 
            
            ph[m] = cnt; // The first m The position of the heap node inserted for the second time is cnt,  Because the value of the heap element is h[cnt]
            hp[cnt] = m; // The first cnt Heap nodes are ph The index in the array is m, That is, the previous line of code ph[m] Medium m, That is to establish a two-way mapping relationship 

            h[cnt] = x;// Assign a value to the inserted heap node 
            up(cnt);// The new node inserted at the bottom of the heap goes up 
        }
        else if(!strcmp(op,"PM"))
        {
    
            cout<<h[1]<<endl;
        }
        else if(!strcmp(op,"DM"))
        {
    
            exchange(1,cnt--);// Exchange the top element of the heap with the end element of the heap 
            down(1);//down operation 
        }
        else if(!strcmp(op,"D"))
        {
    
            cin >> k;
            k = ph[k];// The first k The current position of the number of inserts 
            exchange(k,cnt--);// The first k The current position of the number follows cnt As a parameter , swapping 
            down(k);
            up(k);
        }
        else if(!strcmp(op,"C"))
        {
    
            cin >> k >> x;
            k = ph[k];// For the first k The current position of the number of inserts 
            h[k] = x;// Amendment No k An inserted element 
            down(k);
            up(k);
        }
    }
    
    
    return 0;
}