题解：P11266 【模板】完全体·堆

原题链接

• 洛谷 P11266 【模板】完全体·堆

参考资料

• pb_ds/堆 - OI Wiki

解题思路

说明

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

__gnu_pbds::priority_queue 相比标准库的 std::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;
}