P11266 题解

题目传送门

思路

可以使用 pb_ds 库中的 priority_queue 来解决。

与标准库中的 priority_queue 相同，pb_ds 库中也实现了一个堆。不同的是，pd_ds 库中增加了删除和修改的操作。

下面介绍一下 priority_queue 的基本语法。

priority_queue 的头文件在 bits/extc++.h 中，但由于它不是一个标准 STL 库，还需要引用命名空间 __gnu_cxx。

priority_queue 定义声明方式：__gnu_pbds::priority_queue pq;，在本题中会用到一下的操作：

pq.push(x)：将数字 x 放入堆中。
pq.top()：返回堆顶的元素。
pq.erase(it)：将迭代器 it 从堆中消除。
pq1.join(pq2)：将 pq2 放入 pq1 中，同时清空 pq2。
pq.modify(it,x)：将堆中迭代器为 it 的值改为 x。

AC CODE

CPP

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
__gnu_pbds::priority_queue<int,greater<int>>pq[N];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator p[N];
int main(){
	int n=read(),m=read();
	for(int i=1;i<=n;++i){
		int x=read();
		p[i]=pq[i].push(x);
	}
	while(m--){
		int op=read();
		if(op==0){
			int x=read(),y=read();
			pq[x].erase(p[y]);
		}
		else if(op==1){
			int x=read();
			printf("%d\n",pq[x].top());
		}
		else if(op==2){
			int x=read(),y=read();
			pq[x].join(pq[y]);
		}
		else if(op==3){
			int x=read(),y=read(),z=read();
			pq[x].modify(p[y],z);
		}
	}
	return 0;
}

文章操作

思路

相关推荐

评论

P11266 题解