萌新刚学OI,求助冰茶姬板子

P3367 【模板】并查集

辰星凌 @ 2020-06-17 17:18:28

以前做线段树分治套冰茶姬时一直用的下面这个写法：

inline void merge(Re x,Re y){
    x=find(x),y=find(y);
    if(size[x]>size[y])swap(x,y);
    fa[x]=y,size[y]+=size[x];
}

但是今天复习板子时发现冰茶姬模板题TLE了（不过开了O2后可以20ms过），翻了翻以前代码，意识到按深度合并才是正确的

所以....为啥以前写线段树分治时没出问题啊，有复杂度保证吗？

by FZzzz @ 2020-06-17 17:43:06

@青君不是，线段树分治是另一个东西，这个东西叫并查集（

by UnyieldingTrilobite @ 2020-06-17 17:52:22

@青君不是，线段树分治是另一个东西，这个东西叫并查集（

by UnyieldingTrilobite @ 2020-06-17 17:52:52

线段树分治套UFDS是不是在做离线版动态图完全连通性啊（

by Binary_Search_Tree @ 2020-06-17 17:58:24

按深度合并能卡到O(\sqrt n)

by Binary_Search_Tree @ 2020-06-17 17:58:56

只要我把长度为1\sim\sqrt n的链按深度合并就是O(\sqrt n)

by Binary_Search_Tree @ 2020-06-17 17:59:01

@辰星凌

by Guitar_Jasmine @ 2020-06-17 18:00:00

@Binary_Search_Tree Orz 队爷%%%

by Haishu @ 2020-06-17 18:01:29

@Binary_Search_Tree Orz 队爷%%%

by 辰星凌 @ 2020-06-17 18:01:58

@Binary_Search_Tree 什么意思？能给个简要证明吗？

by iMya_nlgau @ 2020-06-17 18:10:41

@Binary_Search_Tree 问一下，如果一直用路径压缩怎么会产生链呢 /yiw

我一直以为按高度合并也是 O(\alpha (n)) 的 /fad