自动搬运

查看原文

来自洛谷，原作者为

	ikunTLE 互关条件见主页（luogu.me/paste/1ij66blw），关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年8月24日22时50分

搬运于2025-08-24 23:05:53，当前版本为作者最后更新于2025-01-06 21:25:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

可以使用 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

#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;
}