题面

Monkey King

题解

思路很显然，我们对每个猴子和它的朋友的集合维护一个堆，因为每次取出的是最大值，所以我们维护一个大根堆，因为打完架后，猴子互相认识，对应的是合并这两个堆，所以我们要维护的是可合并式堆，于是可以用很好写的左偏树进行维护。
对于削弱操作，直接先把堆顶的猴子取出来，删除这个点，即合并它的左右儿子并把它的左右儿子及左偏树中的 \(dis\) 重置为零，再根据题意，把它的值减半，然后插入到堆中，再合并两个堆即可。对于某个猴子处于哪个集合，我们直接用并查集维护即可，左偏树的细节这里就不赘述了，做了板题应该都清楚，注意改成大根堆即可。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1e5 + 5;

int n, m;

struct Liftist {
	int val[N], dis[N], ls[N], rs[N], rt[N];
	Liftist () { dis[0] = -1 ; }
	int Find(int x) { return x == rt[x] ? x : rt[x] = Find(rt[x]); }
	int merge(int x, int y) {
		if(!x || !y) return x | y;
		if(val[x] < val[y] || (val[x] == val[y] && x < y)) swap(x, y);
		rs[x] = merge(rs[x], y); rt[rs[x]] = x;
		if(dis[rs[x]] > dis[ls[x]]) swap(rs[x], ls[x]);
		dis[x] = dis[rs[x]] + 1;
		return x;
	}
	inline int weak(int x) {
		val[x] >>= 1;
		int root = merge(ls[x], rs[x]);
		ls[x] = rs[x] = dis[x] = 0;
		return rt[x] = rt[root] = merge(root, x);
	}
	inline int Fight(int x, int y) {
		x = Find(x), y = Find(y);
		if(x == y) return -1;
		x = weak(x), y = weak(y);
		rt[x] = rt[y] = merge(x, y);
		return val[rt[x]];
	}
	inline void init() { for(int i = 1; i <= n; i++) ls[i] = rs[i] = dis[i] = 0, rt[i] = i; }
}tr;

int main() {
	while(~scanf("%d", &n)) {
		for(int i = 1; i <= n; i++) scanf("%d", &tr.val[i]);
		scanf("%d", &m); tr.init();
		for(int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), printf("%d\n", tr.Fight(x, y));
	}
	return 0;
}