```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long
#define il inline
#define reg register
const int N = 100005;
int n, m;
int f[N];
struct node {
int val, ch[2], d;
} t[N];
il int qrint() {
int s = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
s = (s << 1) + (s << 3) + (ch ^ 48);
ch = getchar();
}
return s * f;
}
il int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
il int& rs(int x) {
return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d];
}
il int merge(int x, int y) {
if (!x || !y) return x | y;
if (t[x].val < t[y].val) swap(x, y);
rs(x) = merge(rs(x), y);
t[x].d = t[rs(x)].d + 1;
return x;
}
int main() {
while (scanf("%d", &n) != EOF) {
memset(f, 0, sizeof(f));
memset(t, 0, sizeof(t));
for (reg int i = 1; i <= n; ++i) {
t[i].val = qrint();
f[i] = i;
}
scanf("%d", &m);
while (m--) {
int x = find(qrint()), y = find(qrint());
if (x == y) {
printf("%d\n", -1);
continue;
}
int k1, k2, k3, k4, k5;
k1 = f[x] = f[t[x].ch[0]] = f[t[x].ch[1]] = merge(t[x].ch[0], t[x].ch[1]);
t[x].val = t[x].val >> 1, t[x].ch[0] = t[x].ch[1] = 0, t[x].d = 1;
k2 = f[x] = f[k1] = merge(x, k1);
k3 = f[y] = f[t[y].ch[0]] = f[t[y].ch[1]] = merge(t[y].ch[0], t[y].ch[1]);
t[y].val = t[y].val >> 1, t[y].ch[0] = t[y].ch[1] = 0, t[y].d = 1;
k4 = f[y] = f[k3] = merge(y, k3);
k5 = f[k2] = f[k4] = merge(k2, k4);
printf("%d\n", t[k5].val);
}
}
return 0;
}
```
完整代码贴二楼
by Kobe303 @ 2022-02-03 09:59:34
啊其实这题加入新结点时 ```dist``` 初始化为 $0$ 也能过
但隔壁的 [[SCOI2011]棘手的操作](https://www.luogu.com.cn/problem/P3273)
就不一样
[70分，3TLE，dist初始化为0](https://www.luogu.com.cn/record/68469196)
[100分，dist初始化为1](https://www.luogu.com.cn/record/68469206)
by Kobe303 @ 2022-02-03 10:03:44
您竟然已经学了左偏树了%%%
by fjy666 @ 2022-02-03 10:52:50
您竟然已经学了左偏树了%%%
by djwj223 @ 2022-02-03 11:40:45
@[Kobe303](/user/292300) 肯定是你写错了，但是哪里写错了我还在找（
by Acfboy @ 2022-02-04 10:11:39
@[Kobe303](/user/292300) `merge` 里少了个 `pushup`。
by Acfboy @ 2022-02-04 10:19:33
假期坚持偷学，为你点赞！
by WildFlower @ 2022-02-04 10:21:58
@[Acfboy](/user/40318) 哇你怎么看出来的，我瞪了二十分钟啥也没看出来。
by Qiaoqia @ 2022-02-04 10:28:18
@[Qiaoqia](/user/499996) lz 代码写的和 ouuan 的题解一模一样，直接文本比对就好了（
by Acfboy @ 2022-02-04 10:32:18
啊这。
by Qiaoqia @ 2022-02-04 10:38:42