传送门：点击打开链接
题意：很多只猴子，每个猴子有个强壮值，一开始每只猴子都不认识。会有m次冲突，每次冲突的两只猴子如果不认识，就会各自在认识的人中各找一个最强壮的人打架，打完后打赢的那个人的强壮值会减半，并输出减半后的值，然后猴子两边的人都会互相认识成为朋友（所谓不打不相识..），如果两只猴子冲突但是已经认识了，那么就输出-1
思路：左偏树上次翻论文无意中发现的，感觉这种数据结构好666666。。
论文下载地址：点击打开链接
左偏树的优势就在于非常容易写，而且取最小值的复杂度是O(1),弹出和合并的复杂度是O(logn)，因为合并的复杂度非常低，这也使得左偏树的应用可以非常的广泛。
至少在对于许多堆中取最小和最大，并且这些堆会合并的问题中，能很轻易的解决了，那么判断两个是否在同一个堆中，可以利用并查集轻松解决。
这种简单易懂作用十分强大的数据结构很推荐学习，对以后拓宽思路会有非常大的帮助~
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e5 + 5;struct Data {int l, r, key, dist;
} D[MX << 2];
int P[MX], rt[MX];
int rear;int lt_init() {rear = 0;D[0].dist = -1;
}
int lt_new(int _key = 0) {rear++;D[rear].l = D[rear].r = 0;D[rear].key = _key;D[rear].dist = 0;return rear;
}
int lt_merge(int r1, int r2) {if(!r1) return r2;if(!r2) return r1;if(D[r1].key < D[r2].key) {swap(r1, r2);}D[r1].r = lt_merge(D[r1].r, r2);if(D[D[r1].l].dist < D[D[r1].r].dist) {swap(D[r1].l, D[r1].r);}D[r1].dist = D[D[r1].r].dist + 1;return r1;
}
int lt_pop(int &rt) {int ret = D[rt].key;rt = lt_merge(D[rt].l, D[rt].r);return ret;
};
void lt_push(int &rt, int key) {rt = lt_merge(rt, lt_new(key));
}
int find(int x) {return P[x] == x ? x : (P[x] = find(P[x]));
}int main() {int n, m; //FIN;while(~scanf("%d", &n)) {lt_init();for(int i = 1; i <= n; i++) {P[i] = i;}for(int i = 1; i <= n; i++) {int t; scanf("%d", &t);rt[i] = lt_new(t);}scanf("%d", &m);for(int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);int p1 = find(u), p2 = find(v);if(p1 == p2) printf("-1\n");else {rt[p1] = lt_merge(rt[p1], rt[p2]);int ans = lt_pop(rt[p1]) / 2;lt_push(rt[p1], ans);P[p2] = p1;printf("%d\n", ans);}}}return 0;
}