每次给出要争吵的猴子a和b，用并查集判断如果他们是朋友输出-1
如果不是，找出a，b在的堆的根A，B，分别合并A，B的左右孩子，再合并一下。
之后把A，B的数据更改一下：权值除以2，左右孩子设为0，再插入到堆中即可。
最后输出堆顶。
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n, m; 7 int f[100010], w[100010], d[100010], l[100010], r[100010]; 8 9 inline int merge(int x, int y) 10 { 11 if(!x || !y) return x + y; 12 if(w[x] < w[y]) swap(x, y); 13 r[x] = merge(r[x], y); 14 f[r[x]] = x; 15 if(d[l[x]] < d[r[x]]) swap(l[x], r[x]); 16 d[x] = d[r[x]] + 1; 17 return x; 18 } 19 20 inline int find(int x) 21 { 22 return x == f[x] ? x : f[x] = find(f[x]); 23 } 24 25 inline int pop(int x) 26 { 27 int lc = l[x], rc = r[x]; 28 f[lc] = lc; 29 f[rc] = rc; 30 l[x] = r[x] = d[x] = 0; 31 return merge(lc, rc); 32 } 33 34 int main() 35 { 36 int i, j, x, y, fx, fy, x1, y1; 37 while(~scanf("%d", &n)) 38 { 39 for(i = 1; i <= n; i++) 40 { 41 scanf("%d", &w[i]); 42 f[i] = i; 43 l[i] = 0; 44 r[i] = 0; 45 d[i] = 0; 46 } 47 scanf("%d", &m); 48 for(i = 1; i <= m; i++) 49 { 50 scanf("%d %d", &x, &y); 51 fx = find(x); 52 fy = find(y); 53 if(fx == fy) 54 { 55 printf("-1 "); 56 continue; 57 } 58 x1 = pop(fx); 59 w[fx] /= 2; 60 x1 = merge(x1, fx); 61 y1 = pop(fy); 62 w[fy] /= 2; 63 y1 = merge(y1, fy); 64 printf("%d ", w[merge(x1, y1)]); 65 } 66 } 67 return 0; 68 }