Description
如题，一开始有个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：
操作1
将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）
操作2
输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）
Input Format
第一行包含两个正整数，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含个正整数，其中第
个正整数表示第
个小根堆初始时包含且仅包含的数。
接下来行每行
个或
个正整数，表示一条操作，格式如下：
操作1
操作2
Output Format
输出包含若干行整数，分别依次对应每一个操作2所得的结果。
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
对于%的数据：
CCYOS
这是一道左偏树板子题。感谢徐灏诚juju的讲课，挺好理解的。
- 左偏树
可并堆的一种，有如下性质：
a.堆性质
保证每颗子树的根节点的权值小于它的左儿子和右儿子的权值，这样可以删除本堆中的最小节点。
b.左偏性质
定义有一颗子树为空的节点为外节点。
定义每个点的为这个点到它的后代中的外节点的最短距离。
左偏树满足但是这并不代表左偏树左子树比右子树深度大
所以有不可能会出现单右子树的情况，所以令
来使下图的根（外节点）的
权值为5的节点的dist为0
2)左偏树的合并
设有两棵左偏树需要合并。
左偏树的合并是努力让B和A的右子树合并，简称把我的兄弟（？）变成我的儿子，同时要维护左偏树的性质。
a.有一棵树为空：直接返回该子树。
if(!x||!y)return x + y;
b.没有空子树：
为了维护堆性质，选取树。
向下合并，将合并的树的根节点作为
为了维护左偏性质，若左儿子的
更新及左右儿子的
。
返回合并完毕的左偏树
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);
}
注意
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;
}
