有N只孤独的猴子，然后他们会打M次架，每次打架的两只猴子战斗力减半，并且会成为朋友，朋友的朋友也是朋友，问的是朋友中战力最大的猴子是有多少战力？
于是，考虑维护这样的一个大根堆，每次将小的大根堆推给大的，相当于是启发式合并的操作，复杂度。
或者，我们可以直接进行维护，我们维护一个二叉树的“深度”，然后尽量保证深度平衡，也就是使得整棵二叉树的深度尽可能小，所以，我们定义一个dist，表示它和它的子树中的dist最小的值+1，但是这样的维护最后可能退化会形成一条链，不妥，不如我们让左子树的dist大于右子树的dist，然后这样子推下去，最后让根节点的dist等于右子树的dist+1即可。
于是，每次就是合并两棵子树就可以了，合并的时候复杂度为级别，然后删除的时候，实际上就是对左右两棵子树合并，然后插入的时候实际上就是对一个堆大小为1的点的合并了。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define pii pair<int, int> #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 1e5 + 7; int N, M; struct node { int val, d, c[2], fa; node(int a=0, int b=0, int c1=0, int c2=0, int f=0):val(a), d(b), c{c1, c2}, fa(f) {} } t[maxN]; int fid(int x) { return x == t[x].fa ? x : t[x].fa = fid(t[x].fa); } int Merge(int x, int y) { if(!x || !y) return x | y; if(t[x].val < t[y].val) swap(x, y); t[x].c[1] = Merge(t[x].c[1], y); t[t[x].c[1]].fa = x; if(t[t[x].c[0]].d < t[t[x].c[1]].d) swap(t[x].c[0], t[x].c[1]); t[x].d = t[t[x].c[1]].d + 1; return x; } int pop(int x) { t[t[x].c[0]].fa = t[x].c[0]; t[t[x].c[1]].fa = t[x].c[1]; t[x].val >>= 1; int y = Merge(t[x].c[0], t[x].c[1]); memset(t[x].c, 0, sizeof(t[x].c)); return Merge(x, y); } int main() { while(scanf("%d", &N) != EOF) { for(int i=1; i<=N; i++) { scanf("%d", &t[i].val); memset(t[i].c, 0, sizeof(t[i].c)); t[i].fa = i; t[i].d = 0; } scanf("%d", &M); for(int i=1, x, y, fx, fy, ff; i<=M; i++) { scanf("%d%d", &x, &y); fx = fid(x); fy = fid(y); if(fx == fy) { puts("-1"); continue; } if(t[fx].val < t[fy].val) swap(fx, fy); ff = Merge(pop(fx), pop(fy)); printf("%d\n", t[ff].val); } } return 0; }
