题意
给出 \(n\) 个集合 \(S_1 \cdots S_n\),\(S_i = \{a_i\}\),每次给出 \(x,y\),将第 \(x\) 和第 \(y\) 个元素所在的集合的最大值 \(\div 2\),合并两个集合,然后输出新集合的最大值。
sol
每次求出两个集合,记录两个集合的最大值并删除,将两个集合与两个最大值除以 \(2\) 后合并即可。考虑左偏树(可并堆),思路参见 [luoguP3377] 左偏树/可并堆
注意多测要清空
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100005;
struct Node {
int l, r;
int val;
int dist;
}tr[N];
int n, m;
int fa[N];
int find(int x){
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int merge(int x, int y){
if (!x || !y) return x | y;
if (tr[x].val < tr[y].val) swap(x, y);
tr[x].r = merge(tr[x].r, y);
if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
tr[x].dist = tr[tr[x].r].dist + 1;
return x;
}
int main(){
while (scanf("%d", &n) != EOF){
for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].val), tr[i].l = tr[i].r = tr[i].dist = 0, fa[i] = i;
scanf("%d", &m);
while (m -- ){
int x, y;
scanf("%d%d", &x, &y);
int fx = find(x), fy = find(y);
if (fx == fy) puts("-1");
else {
int rtx = merge(tr[fx].l, tr[fx].r), rty = merge(tr[fy].l, tr[fy].r);
tr[fx].val /= 2, tr[fy].val /= 2;
tr[fx].dist = tr[fy].dist = 0;
int xl = tr[fx].l, xr = tr[fx].r, yl = tr[fy].l, yr = tr[fy].r;
tr[fx].l = tr[fx].r = tr[fy].l = tr[fy].r = 0;
fa[fx] = fa[fy] = fa[xl] = fa[xr] = fa[yl] = fa[yr] = merge(merge(rtx, fx), merge(rty, fy));
printf("%d\n", tr[fa[fx]].val);
}
}
}
}
标签:King,dist,Monkey,fa,int,tr,集合,luoguP1456,return
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP1456