洛谷 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;
}