初学左偏树，先做了一个较为简单的题。
题意：有一群猴子，每只猴子都有力量值，不认识的猴子之间可能发生争吵。初始时大家互相不认识（只认识自己）。如果有两只不认识的猴子发生了争吵，那么他们会从各自的朋友里找出力量最强的猴子来格斗，格斗结束后，格斗的两只猴子力量值减半，两个猴子的朋友圈合并。输出决斗完成后，新合并的朋友圈最强猴子的力量值。
左偏树是一种可合并的二叉堆，从名字听就知道它是和平衡树相反。
“它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。”
左偏树的节点包含四个信息：键值(key)，左儿子(l)，右儿子(r)，距离(dis)。
值得注意的是节点中距离的含义是：从自己，到最近的一个没有两个非空节点的子节点的距离。
性质和定义：
1.根节点的键值小于或等于其左右儿子的键值；
2.左儿子的距离不小于右儿子的，显然根节点的距离是右儿子的加一，整个树的根节点的距离不会超过log(n+1)-1；
3.左子树和右子树也是一颗左偏树。
左偏树的操作：
1.合并（假设a和b）：
比较a和b的key值，若a的key值小于等于b的，把b和a的儿子合并。若a的key值大于b，把前面的步骤反过即可。
递归的终点是某个点无右儿子或这个点是空点。
2.删除最小值点（即根节点）：
合并左儿子和右儿子。（简单粗暴啊！）
3.插入：
插入点作为一棵只有一个节点的树，然后和原有的左偏树合并。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 100010
template <class T>
inline int RD(T &x)
{
x = 0;
char ch = getchar();
while(!isdigit(ch)) { ch = getchar(); if(ch == EOF) return 0; }
while(isdigit(ch)) { x *= 10; x += ch - '0'; ch = getchar(); }
return 1;
}
int n, m, s, x, y, fx, fy;
int fa[MAXN];
struct Node
{
int v, l, r, dis;
Node() {}
Node(int _v, int _l, int _r, int _d):
v(_v), l(_l), r(_r), dis(_d) {}
}nn[MAXN];
int find_fa(int x)
{
return fa[x] == x ? x : fa[x] = find_fa(fa[x]);
}
int merge(int x, int y)
{
if(!x) return y;
if(!y) return x;
if(nn[x].v < nn[y].v) swap(x, y);
nn[x].r = merge(nn[x].r, y);
if(nn[nn[x].l].dis < nn[nn[x].r].dis) swap(nn[x].l, nn[x].r);
nn[x].dis = nn[nn[x].r].dis + 1;
return x;
}
int main()
{
// freopen("F.in", "r", stdin);
while(RD(n))
{
for(int i = 1; i <= n; i++)
{
RD(s); fa[i] = i;
nn[i] = Node(s, 0, 0, 0);
}
scanf("%d", &m);
while(m--)
{
RD(x); RD(y);
fx = find_fa(x);
fy = find_fa(y);
if(fx == fy) printf("-1\n");
else
{
x = merge(nn[fx].l, nn[fx].r); nn[fx] = Node(nn[fx].v / 2, 0, 0, 0);
y = merge(nn[fy].l, nn[fy].r); nn[fy] = Node(nn[fy].v / 2, 0, 0, 0);
x = merge(x, y);
x = merge(x, fx);
x = merge(x, fy);
fa[fx] = x;
fa[fy] = x;
fa[x] = x;
printf("%d\n", nn[x].v);
}
}
}
return 0;
}