• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

维护一个最初为空的集合。支持以下操作:

I,插入一个数字x;

PM,输出当前设置中的最小值;

DM,删除当前集合中的最小值(数据保证此时最小值唯一);

d、删除第k个插入的数字;

C x,修改第k个插入的数字,改为x;

现在对于N次操作,对于所有第2次操作,输出当前组的最小值。

输入格式

第一行包含整数n。

接下来的n行,每一行包含一个操作指令,是I x,PM,DM,D k或C K X中的一个。

输出格式

对于每个输出指令PM,输出一个结果,指示当前组中的最小值。

每个结果占一行。

数据范围

1N105

109x109

确保数据合法。

输入样本:

十号州际公路

首相

十号州际公路

D 1

C 2 8

I 6

首相

分米

输出样本:

-10

#includeiostream

# includecstring

#包含算法

#includecstdio

使用命名空间std

const int N=100010

int h[N],cnt//堆数组

int ph[N];//节点号映射到堆数组下标

int HP[N];//堆数组下标映射到节点号

void heap_swap(int a,int b){

swap(ph[hp[a]],ph[HP]);

swap(hp[a],HP);

swap(h[a],h);

}

void down(int u){

int t=u;

if(2 * u=cnth[t]h[2 * u])t=2 * u;

if(2 * u 1=cnth[t]h[2 * u 1])t=2 * u 1;

如果(u!=t){

heap_swap(u,t);

down(t);

}

}

清空(整数)

{

while (u/2 h h[u/2])

{

heap_swap(u,u/2);

u/=2;

}

}

int main(){

int n;

cinn

int idx=0;

while(n - ){

字符串a;

cina

int k,x;

if(a=='I'){

cinx

cnt//堆数组尾下标

idx//记录插入的次数

ph[idx]=cnt,HP[CNT]=idx;

h[CNT]=x;

向上(CNT);

}

else if(a=='PM ')

couth[1]endl;

else if(a=='DM'){

heap_swap(1,CNT);

CNT-;

向下(1);

}

else if(a=='D'){

cink

k=ph[k];//首先将节点号映射到堆数组下标

heap_swap(k,CNT);

CNT-;

向下(k);

up(k);

}

否则{

cinkx

k=ph[k];

h[k]=x;

向下(k);

up(k);

}

}

返回0;

}

https://www.acwing.com/solution/content/5661/

Link to comment
Share on other sites