Description
如題，一開(kāi)始有個(gè)小根堆娩践，每個(gè)堆包含且僅包含一個(gè)數(shù)。接下來(lái)需要支持兩種操作：
操作1
將第x個(gè)數(shù)和第y個(gè)數(shù)所在的小根堆合并（若第x或第y個(gè)數(shù)已經(jīng)被刪除或第x和第y個(gè)數(shù)在用一個(gè)堆內(nèi)烹骨，則無(wú)視此操作）
操作2
輸出第x個(gè)數(shù)所在的堆最小數(shù)翻伺，并將其刪除（若第x個(gè)數(shù)已經(jīng)被刪除，則輸出-1并無(wú)視刪除操作）
Input Format
第一行包含兩個(gè)正整數(shù)沮焕，分別表示一開(kāi)始小根堆的個(gè)數(shù)和接下來(lái)操作的個(gè)數(shù)吨岭。
第二行包含個(gè)正整數(shù)，其中第
個(gè)正整數(shù)表示第
個(gè)小根堆初始時(shí)包含且僅包含的數(shù)峦树。
接下來(lái)行每行
個(gè)或
個(gè)正整數(shù)辣辫，表示一條操作簿废，格式如下：
操作1
操作2
Output Format
輸出包含若干行整數(shù)，分別依次對(duì)應(yīng)每一個(gè)操作2所得的結(jié)果络它。
Sample Input
5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2
Sample Output
1
2
Constraints
對(duì)于%的數(shù)據(jù)：
CCYOS
這是一道左偏樹(shù)板子題。感謝徐灝誠(chéng)juju的講課化戳，挺好理解的单料。
- 左偏樹(shù)
可并堆的一種，有如下性質(zhì)：
a.堆性質(zhì)
保證每顆子樹(shù)的根節(jié)點(diǎn)的權(quán)值小于它的左兒子和右兒子的權(quán)值点楼，這樣可以刪除本堆中的最小節(jié)點(diǎn)扫尖。
b.左偏性質(zhì)
定義有一顆子樹(shù)為空的節(jié)點(diǎn)為外節(jié)點(diǎn)。
定義每個(gè)點(diǎn)的為這個(gè)點(diǎn)到它的后代中的外節(jié)點(diǎn)的最短距離掠廓。
左偏樹(shù)滿足但是這并不代表左偏樹(shù)左子樹(shù)比右子樹(shù)深度大
所以有不可能會(huì)出現(xiàn)單右子樹(shù)的情況换怖，所以令
來(lái)使下圖的根（外節(jié)點(diǎn)）的
權(quán)值為5的節(jié)點(diǎn)的dist為0
2)左偏樹(shù)的合并
設(shè)有兩棵左偏樹(shù)需要合并蟀瞧。
左偏樹(shù)的合并是努力讓B和A的右子樹(shù)合并沉颂，簡(jiǎn)稱把我的兄弟（？）變成我的兒子悦污，同時(shí)要維護(hù)左偏樹(shù)的性質(zhì)铸屉。
a.有一棵樹(shù)為空：直接返回該子樹(shù)。
if(!x||!y)return x + y;
b.沒(méi)有空子樹(shù)：
為了維護(hù)堆性質(zhì)切端，選取樹(shù)彻坛。
向下合并，將合并的樹(shù)的根節(jié)點(diǎn)作為
為了維護(hù)左偏性質(zhì)昌屉，若左兒子的
更新及左右兒子的
间驮。
返回合并完畢的左偏樹(shù)
inline int Merge(int x,int y){
if(!x || !y)return x + y;
if(tr[x].val > tr[y].val)swap(x,y);
if(tr[x].val == tr[y].val && x > y)swap(x,y);
rs = Merge(rs,y);
if(tr[ls].dis < tr[rs].dis)swap(ls,rs);
tr[ls].rt = tr[rs].rt = tr[x].rt = x;
tr[x].dis = tr[rs].dis + 1;
return x;
}
- 左偏樹(shù)的刪除
僅限于刪除最小節(jié)點(diǎn)瘾婿。
inline void Pop(int x){
tr[x].val = -1;
tr[ls].rt = ls;tr[rs].rt = rs;
tr[x].rt = Merge(ls,rs);
}
注意
a) Merge(rs,y)要更新給rs抢呆。
b) 注意題目要求的輸出。
c) tr[0].dist = -1笛谦。
code
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int N,M;
struct tree{
int Ls,Rs,rt,val,dis;
}tr[100005];
inline int read(){
int ret = 0,fl = 1;
char c = getchar();
for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
return fl ? ret : -ret;
}
#define ls tr[x].Ls
#define rs tr[x].Rs
inline int findf(int x){return tr[x].rt == x ? x : tr[x].rt = findf(tr[x].rt);}
inline int Merge(int x,int y){
if(!x || !y)return x + y;
if(tr[x].val > tr[y].val)swap(x,y);
if(tr[x].val == tr[y].val && x > y)swap(x,y);
rs = Merge(rs,y);
if(tr[ls].dis < tr[rs].dis)swap(ls,rs);
tr[ls].rt = tr[rs].rt = tr[x].rt = x;
tr[x].dis = tr[rs].dis + 1;
return x;
}
inline void Pop(int x){
tr[x].val = -1;
tr[ls].rt = ls;tr[rs].rt = rs;
tr[x].rt = Merge(ls,rs);
}
int main(){
// freopen("testdata.in","r",stdin);
// freopen("testdata.out","w",stdout);
N = read();M = read();tr[0].dis = -1;
for(register int i = 1;i <= N;++i)
tr[i].val = read(),tr[i].rt = i;
for(register int i = 1;i <= M;++i){
int op = read();
if(op == 1){
int x = read();int y = read();
if(tr[x].val == -1||tr[y].val == -1)continue;
x = findf(x);y = findf(y);
if(x == y)continue;
tr[x].rt = tr[y].rt = Merge(x,y);
}
else{
int x = read();
if(tr[x].val == -1)printf("-1\n");
else{
x = findf(x);
printf("%d\n",tr[x].val);Pop(x);
}
}
}
return 0;
}
