原题链接： Monkey King
学习自：肖然大佬的视频教程

题意：
一开始有 $n$ 只孤独的猴子，然后他们要打 $m$ 次架，每次打架呢，都会拉上自己朋友最牛叉的出来跟别人打，打完之后战斗力就会减半，每次打完架就会成为朋友（正所谓不打不相识o(∩_∩)o）。
问每次打完架之后那俩猴子最牛叉的朋友战斗力还有多少，若朋友打架就输出 $-1$
$1 \leq n, m \leq 10^5$

线段树合并 并查集

时间复杂度 $O(nlogn)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = 32768;

typedef long long LL;

struct Node{
    int l, r;
    int sz;

    int ld, rd;
}tr[N * 40];

int root[N], idx;

int get_node(int l, int r)
{
    int u = ++ idx;
    tr[u] = {l, r, 0, 0, 0};
    return u;
}

void pushup(int u)
{
    tr[u].sz = tr[tr[u].ld].sz + tr[tr[u].rd].sz;
}

void insert(int &u, int l, int r, int x)
{
    if(!u)  u = get_node(l, r);
    if(l == r)
    {
        tr[u].sz ++;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)  insert(tr[u].ld, l, mid, x);
    else  insert(tr[u].rd, mid + 1, r, x);
    pushup(u);
}

void dele(int u, int x)
{
    if(tr[u].l == tr[u].r)
    {
        tr[u].sz --;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid)  dele(tr[u].ld, x);
    else  dele(tr[u].rd, x);
    pushup(u);
}

int query(int u)
{
    if(tr[u].l == tr[u].r)  return tr[u].l;
    if(tr[tr[u].rd].sz)  return query(tr[u].rd);
    return query(tr[u].ld);
}

int merge(int x, int y)
{
    if(!x or !y)  return x + y;

    int u = x;
    tr[u].sz = tr[x].sz + tr[y].sz;         //  用pushup的话在叶节点会出错
    if(tr[x].ld or tr[y].ld)  tr[u].ld = merge(tr[x].ld, tr[y].ld);
    if(tr[x].rd or tr[y].rd)  tr[u].rd = merge(tr[x].rd, tr[y].rd);
    return u;
}

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

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(root, 0, sizeof root);
        idx = 0;

        for(int i = 1; i <= n; i ++)
        {
            int x;
            scanf("%d", &x);
            insert(root[i], 1, M, x);
            p[i] = i;
        }

        int m;
        scanf("%d", &m);
        while(m --)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            int pa = find(a), pb = find(b);
            if(pa != pb)
            {
                int x = query(root[pa]);
                int y = query(root[pb]);

                dele(root[pa], x);
                dele(root[pb], y);

                insert(root[pa], 1, M, x / 2);
                insert(root[pb], 1, M, y / 2);

                p[pa] = pb;
                root[pb] = merge(root[pa], root[pb]);
                printf("%d\n", query(root[pb]));
            }
            else
                puts("-1");
        }
    }
    return 0;
}