【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1512
【题目大意】
现在有 一群互不认识的猴子，每个猴子有一个能力值，每次选择两个猴子，挑出他们所归属的部落中能力值最强的猴子打架，然后两个最强的猴子能力值减半，之后两个部落就合为一个部落，问每次合并后部落中最强的猴子能力值是多少
【题解】
要求每次取出一堆数字中最大的数字减半再放回去，显然这是优先队列可以完成的操作，但由于之后要将两堆数字合并，所以采用可并优先队列，考虑使用左偏树。在左偏树的维护中同时用并查集维护集合标记的更改，即可以满足题目中所有的要求。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
int n,m,f[N],x,y;
struct Node{
int l,r,d,v;
Node(){}
Node(int _l,int _r,int _d,int _v){l=_l,r=_r,d=_d,v=_v;}
}T[N];
int merge(int a,int b){
if(!a)return b;if(!b)return a;
if(T[a].v<T[b].v)swap(a,b);
T[a].r=merge(T[a].r,b);
f[T[a].r]=a;
if(T[T[a].l].d<T[T[a].r].d)swap(T[a].l,T[a].r);
T[a].d=T[a].r?T[T[a].r].d+1:0;
return a;
}
int pop(int a){
int l=T[a].l,r=T[a].r;
f[T[a].l]=T[a].l;
f[T[a].r]=T[a].r;
T[a].l=T[a].r=T[a].d=0;
return merge(l,r);
}
int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}
int main(){
while(~scanf("%d\n",&n)){
for(int i=1;i<=n;i++){
scanf("%d",&x);
T[i]=Node(0,0,0,x);
f[i]=i;
}scanf("%d",&m);
while(m--){
scanf("%d%d",&x,&y);
x=sf(x),y=sf(y);
if(x==y)puts("-1");
else{
int tx=pop(x),ty=pop(y);
T[x].v/=2; x=merge(x,tx);
T[y].v/=2; y=merge(y,ty);
printf("%d\n",T[merge(x,y)].v);
}
}
}return 0;
}