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

· · 题解

我们初始在序列每个位置建立一个堆。

考虑到本题需要对特定下标的元素进行修改，不妨在堆中存储二元组 (a,b)，表示值为 a，下标为 b 的元素。同时用 w_i 表示下标为 i 的值。这样也可以避免元素值重复的问题。

本题操作中涉及堆的合并，考虑使用启发式合并处理：用 d_i 表示堆 h_i 在序列上的真实位置。初始 d_i=i。将 h_y 合并到 h_x 上时，如果 h_y 中元素较多，则先交换 d_x 和 d_y 的值。

综上，得出四种操作的处理方法：

1 x：输出 h_{d_x} 堆顶元素的第一个键值。

2 x y：如果 h_{d_y} 中的元素多于 h_{d_x}，交换 d_x 和 d_y 的值。依次将 h_{d_y} 中的元素添加到 h_{d_x} 中。及时清空 h_{d_y} 释放内存。

3 x y z：删除 h_{d_x} 中的元素 (w_y,y)，向 h_{d_x} 中添加元素 (z,y)，将 w_y 的值修改为 z。

0 x y：删除 h_{d_x} 中的元素 (w_y,y)。

最后附上参考程序：

#include<bits/stdc++.h>
#define ll long long
#define PII pair<ll,int>

using namespace std;

set<PII> op[1000007];

int dy[1000007];
int wz[1000007];

int n,m,opt,l,r,c;
int dr;
set<PII>::iterator it;
PII tmp;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        dy[i]=i;
        scanf("%d",&dr);
        wz[i]=dr;
        op[i].insert(make_pair(dr,i));
    }
    while(m--){
        scanf("%d%d",&opt,&l);
        if(opt==1){
            it=op[dy[l]].begin();
            printf("%lld\n",(it->first));
        }
        else if(opt==2){
            scanf("%d",&r);
            if(op[dy[l]].size()<op[dy[r]].size()){
                swap(dy[l],dy[r]);
            }
            for(it=op[dy[r]].begin();it!=op[dy[r]].end();it++){
                op[dy[l]].insert(make_pair(it->first,it->second));
            }
            op[dy[r]].clear();
        }
        else if(opt==3){
            scanf("%d%d",&r,&c);
            tmp=make_pair(wz[r],r);
            op[dy[l]].erase(tmp);
            wz[r]=c;
            op[dy[l]].insert(make_pair(c,r));
        }
        else{
            scanf("%d",&r);
            tmp=make_pair(wz[r],r);
            op[dy[l]].erase(tmp);
        }
    }
    return 0;
}