题目:维护一个集合,初始时集合为空,支持如下几种操作:
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,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
蒟蒻错误代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n,m,_size,num;
int q[N];
void down(int u)
{
int t=u;
if(a[t]>=a[2*u]&&2*u<=n) t=2*u;
if(a[t]>=a[2*u+1]&&2*u+1<=n) t=2*u+1;
if(t!=u)
{
swap(a[t],a[u]);
swap(q[t],q[u]);
down(t);
}
}
void up(int u)
{
if(a[u/2]>a[u]&&u!=1)
{
swap(a[u/2],a[u]);
swap(q[u/2],q[u]);
up(a[u/2]);
}
}
void insert(int x)
{
a[++_size]=x;
q[_size]=++num;
up(x);
}
void del(int k)
{
k=q[k];
a[k]=a[_size--];
down(k),up(k);
}
void del_top()
{
del(1);
}
void change(int k,int x)
{
k=q[k];
a[k]=x;
down(k),up(k);
}
int main()
{
int n;
cin>>n;
while(n--)
{
char c[3];
int k,x;
scanf("%s",c);
//puts(c);
if(c[0]=='I')
{
int x;
cin>>x;
insert(x);
}
else if(c[0]=='P')
{
cout<<a[1]<<endl;
}
else if(c[0]=='D')
{
if(c[1]=='M') del_top();
else
{
cin>>k;
del(k);
}
}
else
{
cin>>k>>x;
change(k,x);
}
}
}
有没有大佬告诉哪错了啊QAQ