洛谷 P3377 【模板】左偏树（可并堆）

• 2020 年 7 月 10 日
• 筆記
• 数据结构--可并堆

题目描述

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct trr{
    int dis,val,ls,rs,rt;
}tr[maxn];
/*
dis:记录这个节点到它子树里面最近的叶子节点的距离，叶子节点距离为0
val:节点的权值
ls:左儿子
rs:右儿子
rt:根节点编号
*/
int bing(int xx,int yy){
    if(!xx || !yy) return xx+yy;
    //叶子节点直接返回
    if(tr[xx].val>tr[yy].val ||(tr[xx].val==tr[yy].val && xx>yy)){
        swap(xx,yy);
    }//维护小根堆的性质
    tr[xx].rs=bing(tr[xx].rs,yy);//将xx的右儿子和yy合并
    if(tr[tr[xx].ls].dis<tr[tr[xx].rs].dis) swap(tr[xx].ls,tr[xx].rs);//维护左偏性质
    tr[tr[xx].ls].rt=tr[tr[xx].rs].rt=tr[xx].rt=xx;//维护根节点
    tr[xx].dis=tr[tr[xx].rs].dis+1;//一个节点的距离始终等于右儿子+1
    return xx;
}
int get(int xx){
    if(tr[xx].rt==xx) return xx;
    return tr[xx].rt=get(tr[xx].rt);
    
}//路径压缩查找根节点
void sc(int xx){
    tr[xx].val=-1;
    tr[tr[xx].ls].rt=tr[xx].ls;
    tr[tr[xx].rs].rt=tr[xx].rs;
    tr[xx].rt=bing(tr[xx].ls,tr[xx].rs);
}//删除某个节点
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        tr[i].rt=i;
        scanf("%d",&tr[i].val);
    }
    for(int i=1;i<=m;i++){
        int aa;
        scanf("%d",&aa);
        if(aa==1){
            int bb,cc;
            scanf("%d%d",&bb,&cc);
            if(tr[bb].val==-1 || tr[cc].val==-1) continue;
            int xx=get(bb),yy=get(cc);
            if(xx!=yy) tr[xx].rt=tr[yy].rt=bing(xx,yy);
        } else {
            int bb;
            scanf("%d",&bb);
            if(tr[bb].val==-1) printf("-1\n");
            else {
                printf("%d\n",tr[get(bb)].val);
                sc(get(bb));
            }
        }
    }
    return 0;
}