左偏樹 模闆

左偏樹：

左偏樹是一種可并堆，其具有堆的性質。

以下都以小根堆為例。

對于結點x，val[x]<val[L],val[x]<val[R]。

我們知道如果兩個堆暴力合并是gg的。

左偏樹的特點：顧名思義，堆是一種樹形的結構，而左偏樹就是樹的結點傾向左邊的特殊堆。

左偏樹一些性質不說了，網上基本都有，推薦某篇論文……（忘了= =）

每次合并的時候，隻要一直往右邊找并且合并，

能夠發現最均衡的左偏樹是完全二叉樹，是以隻用logA+logB的時間合并A,B大小的兩個堆。

每次維護左偏樹性質，不滿足則左右兒子交換即可。

剩下的操作都可以用合并實作：

插入：合并新的結點和原來的堆

删除根節點：删除根節點後，将其左右兒子合并。

……

模闆題目：

​​洛谷3377​​

題目描述

如題，一開始有N個小根堆，每個堆包含且僅包含一個數。接下來需要支援兩種操作：

操作1： 1 x y 将第x個數和第y個數所在的小根堆合并（若第x或第y個數已經被删除或第x和第y個數在用一個堆内，則無視此操作）

操作2： 2 x 輸出第x個數所在的堆最小數，并将其删除（若第x個數已經被删除，則輸出-1并無視删除操作）

輸入輸出格式

輸入格式：

第一行包含兩個正整數N、M，分别表示一開始小根堆的個數和接下來操作的個數。

第二行包含N個正整數，其中第i個正整數表示第i個小根堆初始時包含且僅包含的數。

接下來M行每行2個或3個正整數，表示一條操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

輸出格式：

輸出包含若幹行整數，分别依次對應每一個操作2所得的結果。

輸入輸出樣例

輸入樣例#1：

5 5

1 5 4 2 3

1 1 5

1 2 5

2 2

1 4 2

2 2

輸出樣例#1：

1

2

說明

當堆裡有多個最小值時，優先删除原序列的靠前的，否則會影響後續操作1導緻WA。

時空限制：1000ms,128M

資料規模：

對于30%的資料：N<=10，M<=10

對于70%的資料：N<=1000，M<=1000

對于100%的資料：N<=100000，M<=100000

樣例說明：

初始狀态下，五個小根堆分别為:{1}、{5}、{4}、{2}、{3}。

第一次操作，将第1個數所在的小根堆與第5個數所在的小根堆合并，故變為四個小根堆：{1,3}、{5}、{4}、{2}。

第二次操作，将第2個數所在的小根堆與第5個數所在的小根堆合并，故變為三個小根堆：{1,3,5}、{4}、{2}。

第三次操作，将第2個數所在的小根堆的最小值輸出并删除，故輸出1，第一個數被删除，三個小根堆為：{3,5}、{4}、{2}。

第四次操作，将第4個數所在的小根堆與第2個數所在的小根堆合并，故變為兩個小根堆：{2,3,5}、{4}。

第五次操作，将第2個數所在的小根堆的最小值輸出并删除，故輸出2，第四個數被删除，兩個小根堆為：{3,5}、{4}。

故輸出依次為1、2。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char 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=100005;
int n,m;
bool del[N];
struct MHeap{
    int l,r,pre,dist,val;
}heap[N];
int findfa(int x){
    while (heap[x].pre) x=heap[x].pre;
    return x;
}
int Merge(int x,int y){
    if (!x) return y;
    if (!y) return x;
    
    if (heap[x].val>heap[y].val ||
        (heap[x].val==heap[y].val && x>y)) swap(x,y);
    heap[x].r=Merge(heap[x].r,y);
    heap[heap[x].r].pre=x;
    
    if (heap[heap[x].r].dist>heap[heap[x].l].dist)
        swap(heap[x].l,heap[x].r);
        
    heap[x].dist=heap[heap[x].r].dist+1;
    return x;
}
int getmin(int x){
    return heap[findfa(x)].val;
}
void Del(int x){
    int l=heap[x].l,r=heap[x].r;
    heap[heap[x].l].pre=heap[heap[x].r].pre=0;
    heap[x].l=heap[x].r=heap[x].val=0;
    heap[x].dist=-1,del[x]=1;
    Merge(l,r);
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        heap[i].val=read(),del[i]=0;
    int opt,x,y;
    while (m--){
        opt=read(),x=read();
        if (opt==1){
            y=read();
            if (del[x] || del[y]) continue;
            int fx=findfa(x),fy=findfa(y);
            if (fx!=fy) Merge(fx,fy);
        } else
        if (del[x]) puts("-1");
            else printf("%d\n",getmin(x)),Del(findfa(x));
    }
    return 0;
}