题解：P11266 【模板】可并堆 2

lailai0916 · 2024-11-15 19:31:20 · 题解

参考资料

• 堆 - 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;
}