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

也算是对 pb_ds 库中的优先队列各种操作的科普？

一些碎碎念

提醒：你可以不看这部分，这部分算是作者探索未知功能的过程

平常写优先队列的时候一般用不到对值进行修改或者删除的操作，所以我在看这到题的时候在想怎么才能实现题目中的操作，因为我不知道有什么成员函数可以直接获取具体哪个值的迭代器，但是 pb_ds 中却恰好又有这些我所需要的函数，而且都需要迭代器。

首先我是知道 pb_ds 中的所有数据结构支持迭代器访问的，不像标准库的部分数据结构是不支持迭代器的，所以自然而然就想到了 lower_bound ，想着能不能使用，结果却真过编了，但是当然是没用的，这样只会返回错误的迭代器，后面查阅了资料才想起来 pb_ds 的迭代器比较强大，点类型迭代器只要没被删除都保持有效，所以可以直接保存 push 时返回的迭代器，然后在具体操作的时候利用上就是了，我开始还不知道为什么要对某个位置进行操作，现在知道了。

具体实现

推荐阅读资料：

1. OI-Wiki 上对 pb_ds 优先队列的介绍。
2. 该篇博文对 pb_ds 的详细介绍。

首先 push 操作是会返回点类型迭代器的，所以可以在每个元素一开始被插入的时候记录下来，然后在需要的时候直接调用即可。

注意到在一开始就要开出数组来，所以要知道该迭代器类型名，类型名可以通过编译信息返回获得，比较长，目前我没有什么好的解决办法，有大佬知道的话可以分享一下。

类型名：detail::binomial_heap<int, greater<int>, allocator<char>>::point_iterator

其中 binomial_heap 应根据具体使用哪个堆来变化名字。

五种堆均已测试，其中冗余计数二项堆和改良的 Fibonacci 堆（thin_heap）会 MLE，二叉堆会 RE，配对堆和二项堆均可通过，前者稍快一些，且内存偏少，但是差异均不大。

Code

以下是配对堆的模板代码：

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define N 1000010
using namespace std;
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> q[N];
__gnu_pbds::detail::pairing_heap<int, std::greater<int>, std::allocator<char>>::point_iterator id[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	q[1].begin();
	int n, m, opt, x, y, z;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		id[i] = q[i].push(x);
	}
	while (m--)
	{
		cin >> opt;
		if (opt == 1)
		{
			cin >> x;
			cout << q[x].top() << "\n";
		}
		else if (opt == 2)
		{
			cin >> x >> y;
			q[x].join(q[y]);
		}
		else if (opt == 3)
		{
			cin >> x >> y >> z;
			q[x].modify(id[y], z);
		}
		else
		{
			cin >> x >> y;
			q[x].erase(id[y]);
		}
	}
	return 0;
}

具体测试时间效率的时候我加上了快读快写，为了代码简洁性这里给出的是普通的关闭流同步，除了一位大佬手写的超大数据结构外，速度是最快的。