题意：
猴子们打架 认识的猴子不会打架 两仅仅猴子打完以后就认识了 A认识B B认识C A也认识C 每次打架由两伙猴子进行 分别选出自己的最高战斗力 在战斗之后两仅仅猴子战斗力减半 给出m次打架 输出打架后这一伙猴子里的最强战斗力
思路：
推断两仅仅猴子是不是一伙的 用到并查集
高速找出一伙猴子中的最强战斗力用到堆 但打完架两伙猴子合并时堆须要nlogn复杂度 因此用左偏树取代堆
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010 int n,m,tot;
int fa[N];
struct node
{
int v,l,r,dis;
}nd[N]; int getf(int x)
{
if(x!=fa[x]) fa[x]=getf(fa[x]);
return fa[x];
} int newnode(int x)
{
nd[tot].v=x;
nd[tot].l=0;
nd[tot].r=0;
nd[tot].dis=0;
tot++;
return tot-1;
} int merge(int x,int y)
{
if(!x) return y;
if(!y) return x;
if(nd[x].v<nd[y].v) swap(x,y);
nd[x].r=merge(nd[x].r,y);
if(nd[nd[x].l].dis<nd[nd[x].r].dis) swap(nd[x].l,nd[x].r);
nd[x].dis=nd[nd[x].r].dis+1;
return x;
} int pop(int x)
{
int tmp=merge(nd[x].l,nd[x].r);
nd[x].dis=nd[x].l=nd[x].r=0;
return tmp;
} int main()
{
int i,j,fi,fj,x;
while(~scanf("%d",&n))
{
tot=1;
for(i=1;i<=n;i++)
{
scanf("%d",&j);
fa[i]=newnode(j);
}
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&i,&j);
fi=getf(i);
fj=getf(j);
if(fi==fj) puts("-1");
else
{
i=pop(fi);
nd[fi].v/=2;
j=pop(fj);
nd[fj].v/=2;
i=merge(i,j);
i=merge(i,fi);
i=merge(i,fj);
fa[i]=fa[fi]=fa[fj]=i;
printf("%d\n",nd[i].v);
}
}
}
return 0;
}