哇，头晕乎乎
by 胖叽猪羊君 @ 2017-08-25 20:54:48
同学，并查集不支持修改，至少加路径压缩的不行。因为这里合并会改变树的结构所以只能递归每一级慢慢找
by 闪电128812358 @ 2017-08-26 09:50:22
这样搞就可以了
```cpp
# include <iostream>
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# define IL inline
# define RG register
# define ll long long
# define Fill(a, b) memset(a, b, sizeof(a));
using namespace std;
IL ll Read(){
char c = '%'; ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
const int MAXN(100010);
int n, m, fa[MAXN], del[MAXN];
struct Heap{
int key, dis, id;
Heap *ch[2];
IL Heap(RG int val, RG int pos){
key = val; id = pos;
ch[0] = ch[1] = NULL;
}
} *rt[MAXN];
IL int Find(RG int x){
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
IL int Dist(RG Heap *x){
return x == NULL ? 0 : x -> dis;
}
IL void Updata(RG Heap *x){
if(Dist(x -> ch[0]) < Dist(x -> ch[1])) swap(x -> ch[0], x -> ch[1]);
x -> dis = Dist(x -> ch[1]) + 1;
}
IL Heap *Merge(RG Heap *x, RG Heap *y){
if(x == NULL) return y;
if(y == NULL) return x;
if(y -> key < x -> key) swap(x, y);
x -> ch[1] = Merge(x -> ch[1], y);
Updata(x);
return x;
}
IL void Delete(RG Heap *&x){
RG Heap *tmp = x;
del[tmp -> id] = 1;
x = Merge(x -> ch[0], x -> ch[1]);
delete tmp;
}
int main(){
n = Read(); m = Read();
for(RG int i = 1, a; i <= n; i++){
a = Read(); fa[i] = i;
rt[i] = new Heap(a, i);
}
while(m--){
RG int opt = Read();
if(opt == 1){
RG int x = Read(), y = Read(), fx = Find(x), fy = Find(y);
if(fx == fy || del[x] || del[y]) continue;
rt[fx] = Merge(rt[fx], rt[fy]);
fa[fy] = fx;
}
else{
RG int x = Read(), fx = Find(x);
if(del[x]){
printf("-1\n");
continue;
}
printf("%d\n", rt[fx] -> key);
Delete(rt[fx]);
}
}
return 0;
}
```
by Cyhlnj @ 2017-08-30 11:41:44
比如你要删除一个节点
如果不加路径压缩的话
理论上（实际上也是）一个点儿子节点最多两个（从并查集的角度上来讲）
当你将堆的顶节点删除时，只需要修改他的儿子的父节点就可以了（查询是O（1），因为儿子节点已经记录了，为左右儿子）
但如果加上路径压缩的话，那么堆顶的节点的儿子数是n个，并且你需要一个个修改到删除后对应的堆的堆顶，但实际上你的删除操作中并没有进行这样的操作
by eight_cloud_purple @ 2018-04-02 23:09:53