题目
https://www.luogu.com.cn/problem/P2713
这题面真的不是十一抽杀吗？
思路
没有什么可说的思路，就是一道可并堆的模板题。用左偏树实现是比较简单的一种方式。
简单介绍一下左偏树。
一些定义：
外结点：左子树或右子树为空的结点。
距离：结点(i)的距离为(i)到它的后代中最近的外结点的边数。
左偏树满足左偏性质：任意结点的左子结点的距离(geq)右子结点的距离（这个依赖于后面的merge操作来维护），所以，一个结点的距离等于该从该节点开始的最右路径的长度。
于是，一个(n)个结点的左偏树的距离(leq lfloorlog_2(n+1) floor -1)（抄书上的，不会严格证明，意会就完事了）。
左偏树的核心操作是合并两棵树（如果往树中添加元素，可以看成是与一棵只有根节点的树合并）。设当前两棵树的根节点分别为x,y,不妨令val(x)(leq)val(y)。
我们递归下去，始终让y与x的右子树合并（每当遇到val(x)>val(y)的情况时就交换xy），直到有一个值为0。
语言表达不是很清楚，下面是伪代码：
Function Merge(A,B)
If A == NULL Then return B
If b == NULL Then return A
if val(A) < val（B）Then swap(A,B)
right(A)=Merge(right(A),B)
If dis(right(A)) > dis(left(A)) Then swap(left(A),right(A))
If right(A) == NULL Then dis(A)=0
Else dis(A) = dis(right(A))+1
return A
End Function
寻找根节点就暴力往上跳就好了。
对于删除最小值的操作，我们找到根节点，删掉它，合并左右子树（记得先把左右子树的父亲值清零）。
大概就这些了，对数据结构感兴趣的同学可以看一下这本书高级数据结构——林厚从，接下来是本题代码：
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn (int)(1e6+10)
using namespace std;
int book[maxn];
struct LTree{
int val,fa,lson,rson,len;
} tree[maxn];
int getf(int x){
if(!tree[x].fa) return x;
return getf(tree[x].fa);
}
int merge(int x,int y){
if(tree[x].val>tree[y].val) swap(x,y);
if(!x) return y;
if(!y) return x;
tree[x].rson=merge(tree[x].rson,y);
if(tree[x].lson) tree[tree[x].lson].fa=x;
if(tree[x].rson) tree[tree[x].rson].fa=x;
if(tree[tree[x].rson].len>tree[tree[x].lson].len)
swap(tree[x].lson,tree[x].rson);
if(tree[x].rson) tree[x].len=tree[tree[x].rson].len+1;
else tree[x].len=0;
return x;
}
void MERGE(int x,int y){
if(book[x]||book[y]) return;
int f1=getf(x),f2=getf(y);
if(f1!=f2) merge(f1,f2);
return;
}
int remove(int x){
if(book[x]) return 0;
book[x]=1;
tree[tree[x].lson].fa=tree[tree[x].rson].fa=0;
merge(tree[x].lson,tree[x].rson);
return tree[x].val;
}
int main(){
int n,m,i,x,y;
char f[5];
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&tree[i].val);
scanf("%d",&m);
for(i=1;i<=m;++i){
scanf("%s",f);
if(f[0]=='M'){
scanf("%d%d",&x,&y);
MERGE(x,y);
}
if(f[0]=='K'){
scanf("%d",&x);
printf("%d
",remove(getf(x)));
}
}
// system("pause");
return 0;
}