AcWing 839. 模拟堆
原题链接
简单
作者:
Obsess_7
,
2022-04-20 21:17:56
,
所有人可见
,
阅读 147
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int d[N],n,idx,i;
int ix[N];//第i个插入的数在d[N]中的下标为ix[i]
int xi[N];//d[i]为第xi[i]插入的数
void deap_swap(int a,int b)
{
swap(ix[xi[a]],ix[xi[b]]);
/*
原理:
ix[a]=b,xi[b]=a;
ix[xi[b]]=a;
if a=1,b=2;
ix[5]=1;xi[1]=5;
ix[2]=6;xi[6]=2;
如果是swap(ix[1],ix[2])因为a,b是堆的下标而不是代表第几个插入,所以要转换成第几个插入的就要hp[a],hp[b];
*/
swap(xi[a],xi[b]);
swap(d[a],d[b]);
}
void down(int x)
{
int t=x;
if(x*2<=idx&&d[x*2]<d[t])t=x*2;
if(x*2+1<=idx&&d[x*2+1]<d[t])t=x*2+1;
if(t!=x)
{
deap_swap(x,t);
down(t);
}
}
void up(int x)
{
while(x/2>=1&&d[x]<d[x/2])
{
deap_swap(x,x/2);
x=x/2;
}
}
int main()
{
string s;
cin>>n;
while (n -- )
{
int a;
cin>>s;
if(s=="I")
{
cin>>a;
idx++;
i++;
d[idx]=a;
ix[i]=idx;
xi[idx]=i;
up(idx);
}
else if(s=="PM")
{
cout<<d[1]<<endl;
}
else if(s=="DM")
{
deap_swap(1,idx);
idx--;
down(1);
}
else if(s=="D")
{
int k;
cin>>k;
k = ix[k];
deap_swap(k,idx);
idx--;
up(k);
down(k);
}
else if(s=="C")
{
int k,x;
cin>>k>>x;
k = ix[k];
d[k]=x;
up(k);
down(k);
}
}
}