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

LEE114514 · 2024-11-10 15:39:43 · 题解

思路

首先这个题显然平衡树是能做的，但是堆常数上会更优秀。

具体的，我们使用可并堆实现。

对于一个集合，我们维护两个小根堆，pq1 表示未被实际弹出（后面解释）的元素，pq2 表示应该删除的元素。

• 对于插入操作，我们往 pq1 内直接插入。

• 对于删除操作，我们往 pq2 内插入对应元素。

• 对于查询操作，我们检验 pq2 是否非空且堆顶元素与 pq1 堆顶相等，如果是则从两个堆中同时弹出堆顶。重复上述操作直至不满足条件，此时 pq1 的堆顶就是最小值。

• 对于合并操作，我们直接分别合并两个集合的 pq1,pq2。

• 对于赋值操作，转化为一次删除和一次插入。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

struct node2{
    __gnu_pbds::priority_queue<int> pq1,pq2;
    void ins(int x){
        pq1.push(-x);
    }
    void del(int x){
        pq2.push(-x);
    }
    int getmin(){
        while(!pq2.empty()&&pq2.top()==pq1.top()) pq1.pop(),pq2.pop();
        return -pq1.top();
    }
};
void merge(node2 *x,node2 *y){
    x->pq1.join(y->pq1);
    x->pq2.join(y->pq2);
}
const int maxn=1e6+5;
int a[maxn];
node2 *s[maxn];
int n,m;
int op,x,y,z;
int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i){
        s[i]=new node2;
        scanf("%d",a+i),s[i]->ins(a[i]);
    }

    while(m--){
        scanf("%d%d",&op,&x);
        if(op==0){
            scanf("%d",&y);
            s[x]->del(a[y]);
        }else if(op==1){
            printf("%d\n",s[x]->getmin());
        }else if(op==2){
            scanf("%d",&y);
            merge(s[x],s[y]);
        }else{
            scanf("%d%d",&y,&z);
            s[x]->ins(z);
            s[x]->del(a[y]);
            a[y]=z;
        }
    }
}