题目地址：

https://www.luogu.com.cn/problem/P1456

题面翻译：
题目描述：
曾经在一个森林中居住着$N$只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。

假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如$10$会减少到$5$，而$5$会减少到$2$，即向下取整）。

我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

输入格式：
有多组数据，每一组数据有两部分。
第一部分：第一行包含一个整数$N$表示猴子的数量。后为$N$行，每行一个数字为第$i$只猴子的强壮值$s_i$。
第二部分：第一行包含一个整数$M$表示发生了$M$次冲突。后为$M$行，每行两个整数$x$和$y$，表示第$x$只猴子和第$y$只猴子之间发生了冲突。

输出格式：
对于每次冲突，如果两只猴子认识对方，输出-1，否则输出决斗后他们朋友中最强壮的猴子的强壮值。

数据范围：
$N,M\le 100000$，$s_i\le 32768$

题目描述：
Once in a forest, there lived $N$ aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can’t avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.
Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, $10$ will be reduced to $5$ and $5$ will be reduced to $2$).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

输入格式：
There are several test cases, and each case consists of two parts.
First part: The first line contains an integer $N(N\le 100,000)$, which indicates the number of monkeys. And then $N$ lines follows. There is one number on each line, indicating the strongness value of ith monkey($\le 32768$).
Second part: The first line contains an integer $M(M\le 100,000)$, which indicates there are $M$ conflicts happened. And then $M$ lines follows, each line of which contains two integers $x$ and $y$, indicating that there is a conflict between the $X$th monkey and $Y$th.

输出格式：
For each of the conflict, output $-1$ if the two monkeys know each other, otherwise output the strength value of the strongest monkey among all of its friends after the duel.

可以用左倾堆 + 并查集，这里需要用大顶堆，每个并查集对应一个大顶堆，并且维护并查集的树根即为该大顶堆的堆顶。每次询问的时候，先查询一下$x$和$y$所在堆的堆顶，这两个即为强壮值最大的两个猴子（如果堆顶相等则说明不需要决斗），做决斗的时候，先合并$x$和$y$的左右子堆，最后将$x$和$y$的强壮值减半，再合并进去。并查集的维护只需要直接将$x$和$y$还有最终合并出来的堆的堆顶$t$的父亲全连到$t$上即可。代码如下：

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int v[N], d[N], l[N], r[N];
int p[N];

int find(int x) {
    
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

int merge(int x, int y) {
    
  if (!x || !y) return x ^ y;
  if (v[x] < v[y]) swap(x, y);
  r[x] = merge(r[x], y);
  if (d[l[x]] < d[r[x]]) swap(l[x], r[x]);
  d[x] = d[r[x]] + 1;
  return x;
}

int main() {
    
  while (~scanf("%d", &n)) {
    
    for (int i = 1; i <= n; i++) {
    
      scanf("%d", &v[i]);
      p[i] = i;
      d[i] = 1;
      l[i] = r[i] = 0;
    }

    scanf("%d", &m);
    while (m--) {
    
      int x, y;
      scanf("%d%d", &x, &y);
      x = find(x), y = find(y);
      if (x == y) puts("-1");
      else {
    
        int t = merge(merge(l[x], l[y]), merge(r[x], r[y]));
        l[x] = r[x] = l[y] = r[y] = 0;
        v[x] /= 2, v[y] /= 2;
        t = merge(t, merge(x, y));
        p[x] = p[y] = p[t] = t;
        printf("%d\n", v[t]);
      }
    }
  }
}

每次操作时间复杂度$O(\log N)$，空间$O(N)$。