P11266 【模板】可并堆 2

参考资料

• 堆 - OI Wiki

解题思路

说明

本题使用 GNU PBDS（Policy-Based Data Structures）可以非常优雅地解决。

__gnu_pbds::priority_queue 相比标准库的 std::priority_queue 提供了更灵活的修改和删除操作。

函数

__gnu_pbds::priority_queue 支持以下函数：

• push(x)：向堆中压入元素 x，返回该元素位置的迭代器。
• erase(it)：把迭代器 it 位置的键值从堆中擦除。
• top()：返回堆顶元素。
• join(x)：把堆 x 合并到 *this 并把 x 清空。
• modify(it,x)：把迭代器 it 位置的键值修改为 x，并对底层储存结构进行排序。

实现

初始时，将每个数 $a_i$ 压入堆 $q_i$，并记录其迭代器的位置 $it_i$。

对于每次操作：

• 0 x y：使用 erase(it) 在 $q_x$ 删除 $it_y$ 位置的键值。
• 1 x：使用 top() 查询 $q_x$ 堆顶元素（即最小值）。
• 2 x y：使用 join(x) 把 $q_x$ 合并到 $q_y$ 并把 $q_x$ 清空。
• 3 x y z：使用 modify(it,x) 把 $q_x$ 中 $it_y$ 位置的键值修改为 $x$。

代码非常简洁，缺点是常数较大。

参考代码

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

const int N=1000005;
__gnu_pbds::priority_queue<int,greater<int>> q[N];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator it[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){int x;cin>>x;it[i]=q[i].push(x);}
	while(m--)
	{
		int op,x,y,z;
		cin>>op;
		if(op==0){cin>>x>>y;q[x].erase(it[y]);}
		else if(op==1){cin>>x;cout<<q[x].top()<<'\n';}
		else if(op==2){cin>>x>>y;q[x].join(q[y]);}
		else if(op==3){cin>>x>>y>>z;q[x].modify(it[y],z);}
	}
	return 0;
}