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

· · 题解

首先我们要知道一个东西：pbds 的 priority_queue，跟我们日常使用的那个堆名字一样。

OI-WIKI 简介。

本题需要以下操作：

  1. push()：向堆中压入一个元素，返回该元素位置的迭代器。
  2. top()：返回堆顶元素。
  3. modify(point_iterator, const key)：把迭代器位置的 key 修改为传入的 key，并对底层储存结构进行排序。
  4. erase(point_iterator)：把迭代器位置的键值从堆中擦除。
  5. join(__gnu_pbds::priority_queue &other)：把 other 合并到 *this 并把 other 清空。

当然，这题和 P3377 那题的要求有所不同，注意到 modify 和 erase 操作需要迭代器，而那题不需要这两个操作，所以这题要记录迭代器位置。

然后需要注意的是即使你已经 using namespace __gnu_pbds; 仍需要在声明此数据结构前添加 __gnu_pbds::，因为它与 bits/stdc++.h 库的 priority_queue 重名。

代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
using pair_heap=__gnu_pbds::priority_queue<int,greater<int>>;
const int N=1e6+1;
int n,m,op,x,y,z;
pair_heap q[N];
pair_heap::point_iterator id[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>x,id[i]=q[i].push(x);
    while(m--){
        cin>>op;
        if(op==0) cin>>x>>y,q[x].erase(id[y]);
        if(op==1) cin>>x,cout<<q[x].top()<<endl;
        if(op==2) cin>>x>>y,q[x].join(q[y]);
        if(op==3) cin>>x>>y>>z,q[x].modify(id[y],z);
    }
}