qwq 又是这样 上次就是数组开小了导致re 然后对着一份完全正确的代码看了一个多小时

这次是看了半个多小时

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

#define N 32768

using namespace std;

const int M = 1e5 + 10;

// 权值线段树
struct Node{
    int l, r;
    int lc, rc;
    int sz; // 记录大小
}sgt[M * 70];
int root[M], cnt;

void pushup(int u){
    sgt[u].sz = sgt[sgt[u].lc].sz + sgt[sgt[u].rc].sz;
}

int newnode(int l,int r){
    sgt[ ++ cnt].lc = 0;
    sgt[cnt].rc = 0;
    sgt[cnt].l = l, sgt[cnt].r = r;
    sgt[cnt].sz = 0;
    return cnt;
}

void insert(int &p,int l,int r,int x){
    if(!p) p = newnode(l, r);
    if(l == r) { ++ sgt[p].sz; return ; }
    int mid = l + r >> 1;
    if(x <= mid) insert(sgt[p].lc, l, mid, x);
    else insert(sgt[p].rc, mid + 1, r, x);
    pushup(p);
}

void del(int &p,int x){
    if(!p) return ;
    if(sgt[p].l == sgt[p].r) { -- sgt[p].sz; return ; } // 这里可以对每个节点直接判断就不用pushup了
    int mid = sgt[p].l + sgt[p].r >> 1;
    if(x <= mid) del(sgt[p].lc, x);
    else del(sgt[p].rc, x);
    pushup(p);
}
/*
void del(int &p,int x){
    if(!p) return ;
    -- sgt[p].sz;
    if(sgt[p].l == sgt[p].r) return ;
    int mid = sgt[p].l + sgt[p].r >> 1;
    if(x <= mid) del(sgt[p].lc, x);
    else del(sgt[p].rc, x);
    // pushup(p);
}
*/
int query(int &p){
    if(!p) return 0;
    if(sgt[p].l == sgt[p].r) return sgt[p].l;
    if(sgt[sgt[p].rc].sz) return query(sgt[p].rc);
    else return query(sgt[p].lc);
}

int merge(int &p,int &q,int l,int r){
    if(!p || !q) return p + q;
    if(l == r){ // 叶子节点
        sgt[p].sz += sgt[q].sz;
        return p;
    }
    // 递归处理左右子树
    int mid = l + r >> 1;
    // sgt[p].sz = sgt[p].sz + sgt[q].sz;
    sgt[p].lc = merge(sgt[p].lc, sgt[q].lc, l, mid);
    sgt[p].rc = merge(sgt[p].rc, sgt[q].rc, mid + 1, r);
    pushup(p);
    return p; // 删除 q
}

int n, m;
int p[M];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){

    while(scanf("%d", &n) != EOF){
        memset(root, 0, sizeof root), cnt = 0;
        int x;
        for(int i = 1;i <= n;i ++ ){
            p[i] = i;
            scanf("%d", &x);
            insert(root[i], 1, N, x);
        }

        scanf("%d", &m);
        int y, rx, ry;
        while(m -- ){
            scanf("%d%d", &x, &y);
            rx = find(x), ry = find(y);
            if(rx == ry){
                puts("-1");
                continue;
            }

            x = query(root[rx]);
            y = query(root[ry]);

            del(root[rx], x);
            del(root[ry], y);

            insert(root[rx], 1, N, x / 2);
            insert(root[ry], 1, N, y / 2);

            p[rx] = ry;
            root[ry] = merge(root[rx], root[ry], 1, N);

            printf("%d\n", query(root[ry]));
        }
    }

    return 0;
}