hdu 1512 Monkey King 左偏树

这题意思是一群一开始互不认识的猴子，可能会打架，打过一场就是朋友，一开始互不相识的猴子打架的时候，不一定自己动手，回去找自己朋友中战斗力最强的猴子，然后，两个打手打架，当然，如果自己最NB时，自己上，但是，打完之后，两只参战的猴子战斗力减半，但是，两方会成为朋友。说了这么多废话，就是建立一堆大顶堆，并且实现堆与堆的合并，利用左偏树是可并堆的特点，进行模拟即可，如果两方在一个朋友圈里，输出“-1”。

/*
Memory: 2184 KB        Time: 406 MS
Language: C++        Result: Accepted
By coolwind
Note:这个写的略搓，通用性有点差，做zoj3512,因为这个模板WA了几回
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
struct Node{int l;int r;int val;int dis;int pre;
}LHeap[MAXN];int Merge(int a, int b)
{if(a == 0) return b;if(b == 0) return a;if(LHeap[b].val > LHeap[a].val) swap(a,b);LHeap[a].r = Merge(LHeap[a].r,b);LHeap[LHeap[a].r].pre = a;if(LHeap[LHeap[a].r].dis > LHeap[LHeap[a].l].dis)swap(LHeap[a].l,LHeap[a].r);if(LHeap[a].r == 0) LHeap[a].dis = 0;else LHeap[a].dis = LHeap[LHeap[a].r].dis + 1;return a;
}int pop(int x)
{int l = LHeap[x].l;int r = LHeap[x].r;LHeap[l].pre = l;LHeap[r].pre = r;LHeap[x].l = LHeap[x].r = LHeap[x].dis = 0;return Merge(l,r);
}int find(int x)
{if(LHeap[x].pre == x)return x;return find(LHeap[x].pre);
}int main()
{int n,m;int a, b;int i;while(~scanf("%d",&n)){for(i = 1; i <= n; i ++){scanf("%d",&LHeap[i].val);LHeap[i].l = LHeap[i].r = LHeap[i].dis = 0;LHeap[i].pre = i;}scanf("%d",&m);while(m --){scanf("%d%d",&a,&b);int fa = find(a);int fb = find(b);if(fa == fb){printf("-1\n");continue;}LHeap[fa].val /= 2;int u = pop(fa);u = Merge(u,fa);LHeap[fb].val /= 2;int v = pop(fb);v = Merge(v,fb);printf("%d\n",LHeap[Merge(u,v)].val);}}return 0;
}