AcWing T839

#include 
#include 
#define N 100002
using namespace std;
int h[N], ph[N], hp[N], now;//堆 heap
void _swap(int a, int b) {//heap_swap
	swap(h[a], h[b]);
	swap(hp[a], hp[b]);
	swap(ph[hp[a]], ph[hp[b]]);
}
void up(int a) {
	if (a / 2 > 0 && h[a] < h[a / 2]) {
		_swap(a, a / 2);
		up(a / 2);//递归操作
	}
}
void down(int a) {
	int t = a;
	if (a * 2 <= now && h[t] > h[a * 2]) t = a * 2;
	if (a * 2 + 1 <= now && h[t] > h[a * 2 + 1])  t = a * 2 + 1;
	if (a != t)
	{
		_swap(a, t);
		down(t);//递归操作
	}
}
int main() {
	int n,m=0;
	scanf("%d", &n);
	char st[5];
	for (int i = 1; i <= n; i++) {
		int k, x;
		scanf("%s", st);
		if (st[0] == 'I') {
			scanf("%d", &x);
			m++;
			h[++now] = x;
			ph[m] = now;
			hp[now] = m;
			up(now);
		}
		else if (st[0] == 'C') {
			scanf("%d%d", &k, &x);
			h[ph[k]] = x;
			down(ph[k]);
			up(ph[k]);
		}
		else if (st[0] == 'D' && st[1] == 'M') {
			_swap(1, now);
			now--;
			down(1);
		}
		else if (st[0] == 'P' && st[1] == 'M') {
			printf("%dn", h[1]);
		}
		else {
			cin >> k;
			int t = ph[k];
			_swap(t, now); 
			now--;
			up(t);
			down(t);
		}
	}
	return 0;
}