bzoj1455——罗马游戏
1、题目大意:维护一个数据结构,可以实现合并操作,还能询问最小值
2、分析:这种问题当然是可并堆啦
3、代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1200000
struct merge_heap{
int l[M], r[M], d[M], value[M];
void init(){
memset(l, 0, sizeof(r));
memset(r, 0, sizeof(r));
memset(d, 1, sizeof(d));
}
int merge(int x, int y){
if(!x) return y;
if(!y) return x;
if(value[x] > value[y]) swap(x, y);
r[x] = merge(r[x], y);
if(d[l[x]] < d[r[x]]){
swap(l[x], r[x]);
}
d[x] = d[l[x]] + 1;
return x;
}
} wt;
int fa[M], tree[M], died[M];
int find(int x){
if(fa[x] == x) return x;
int k = find(fa[x]);
fa[x] = k;
return k;
}
int main(){
int n, m;
scanf("%d", &n);
wt.init();
for(int i = 1; i <= n; i ++){
scanf("%d", &wt.value[i]);
fa[i] = i;
tree[i] = i;
}
scanf("%d", &m);
char str[5];
int a, b;
for(int i = 1; i <= m; i ++){
scanf("%s", str);
if(str[0] == 'M'){
scanf("%d%d", &a, &b);
if(died[a] || died[b]) {
continue;
}
if(find(a) != find(b)){
int af = find(a), bf = find(b);
fa[af] = bf;
tree[bf] = wt.merge(tree[af], tree[bf]);
}
}
else{
scanf("%d", &a);
if(died[a]){
printf("0\n");
continue;
}
int af = find(a);
died[tree[af]] = 1;
printf("%d\n", wt.value[tree[af]]);
tree[af] = wt.merge(wt.l[tree[af]], wt.r[tree[af]]);
}
}
return 0;
}