题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
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≤10^5$
$−10^9≤x≤10^9$
数据保证合法。
样例
输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例:
-10
6
算法
模拟堆
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
// h[N]存储堆
// cnt存储节点的数量(正在使用的节点的下标), 从1开始
int h[N], cnt;
// ph[k]存储第 k 个插入的点的下标
// hp[i]存储下标为 i 的点为第几个插入的点
// 即如果 ph[k] = i, 则hp[i] = k;
// 即如果 ph[3] = 2, 则hp[2] = 3
int ph[N], hp[N];
// 交换
void heap_swap(int u, int t)
{
swap(ph[hp[u]], ph[hp[t]]); // 此时hp[u]和hp[t]没有变, 仍然表示下标为u的点是第几个插入的
swap(hp[u], hp[t]); // 交换
swap(h[u], h[t]);
}
// 节点下移
void down(int u)
{
int t=u;
if (u*2 <= cnt && h[u*2] < h[t]) t = u*2;
if (u*2+1 <= cnt && h[u*2+1] < h[t]) t = u*2+1;
if (u!=t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u/2 && h[u/2] > h[u])
{
heap_swap(u/2, u);
u /= 2;
}
}
int main()
{
// m用来记录第几个插入的点
int n, m = 0;
scanf("%d", &n);
while(n--)
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I")) // 插入
{
scanf("%d", &x);
m++, cnt++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if(!strcmp(op, "PM")) // 查询
{
printf("%d\n", h[1]);
}
else if(!strcmp(op, "DM")) // 删除最小值
{
heap_swap(1, cnt);
cnt--;
down(1);
}
else if(!strcmp(op, "D")) // 删除第k个值
{
scanf("%d", &k);
k = ph[k]; // 获取对应下标
heap_swap(k, cnt);
cnt--;
down(k), up(k);
}
else
{
scanf("%d%d", &k, &x);
k=ph[k];
h[k]=x;
down(k), up(k);
}
}
return 0;
}