题解：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;
}