题意
原题链接
维护一个数据结构,要求支持合并集合或删除集合最小值并输出。
sol
双倍经验,同 [luoguP3377] 左偏树/可并堆
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000005;
struct Node{
int l, r;
int val;
int dist;
} tr[N];
int n, m;
bool st[N];
int fa[N];
int find(int x){
if (fa[x] == 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(){
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].val), fa[i] = i;
scanf("%d", &m);
while (m -- ){
char op[2];
int x, y;
scanf("%s", op);
if (*op == 'M') {
scanf("%d%d", &x, &y);
int fx = find(x), fy = find(y);
if (st[x] || st[y] || fx == fy) continue;
fa[fx] = fa[fy] = merge(fx, fy);
}
else {
scanf("%d", &x);
int fx = find(x);
if (st[x]) puts("0");
else {
printf("%d\n", tr[fx].val);
st[fx] = true;
fa[tr[fx].l] = fa[tr[fx].r] = fa[fx] = merge(tr[fx].l, tr[fx].r);
}
}
}
}
标签:luoguP2713,dist,游戏,val,int,罗马,tr,fa,return
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP2713