P11266 题解

ikunTLE · 2025-01-06 21:25:23 · 题解

题目传送门

思路

可以使用 pb_ds 库中的 priority_queue 来解决。

与标准库中的 priority_queue 相同，pb_ds 库中也实现了一个堆。不同的是，pd_ds 库中增加了删除和修改的操作。

下面介绍一下 priority_queue 的基本语法。

priority_queue 的头文件在 bits/extc++.h 中，但由于它不是一个标准 STL 库，还需要引用命名空间 __gnu_cxx。

priority_queue 定义声明方式：__gnu_pbds::priority_queue pq;，在本题中会用到一下的操作：

• pq.push(x)：将数字 x 放入堆中。
• pq.top()：返回堆顶的元素。
• pq.erase(it)：将迭代器 it 从堆中消除。
• pq1.join(pq2)：将 pq2 放入 pq1 中，同时清空 pq2。
• pq.modify(it,x)：将堆中迭代器为 it 的值改为 x。

AC CODE

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
__gnu_pbds::priority_queue<int,greater<int>>pq[N];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator p[N];
int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i){
        int x=read();
        p[i]=pq[i].push(x);
    }
    while(m--){
        int op=read();
        if(op==0){
            int x=read(),y=read();
            pq[x].erase(p[y]);
        }
        else if(op==1){
            int x=read();
            printf("%d\n",pq[x].top());
        }
        else if(op==2){
            int x=read(),y=read();
            pq[x].join(pq[y]);
        }
        else if(op==3){
            int x=read(),y=read(),z=read();
            pq[x].modify(p[y],z);
        }
    }
    return 0;
}