辰星凌 @ 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 iMya_nlgau @ 2020-06-17 18:14:38
就算不用路径压缩，按高度合并也是
by iotang @ 2020-06-17 18:23:42
提 高 组 初 赛
by AgrumeStly @ 2020-06-17 18:34:16
提 高 组 初 赛
by Binary_Search_Tree @ 2020-06-17 19:25:58
@辰星凌 哎我说的线段树分治套并查集
by Binary_Search_Tree @ 2020-06-17 19:26:30
@辰星凌 不是这题。。。
by 辰星凌 @ 2020-06-17 19:27:41
@Binary_Search_Tree 谔谔那size会不会被卡
by Binary_Search_Tree @ 2020-06-17 19:28:17
@辰星凌 就是不能路径压缩的时候只按深度合并时错的
by Binary_Search_Tree @ 2020-06-17 19:28:50
@辰星凌 按size合并没路径压缩是严格
by 辰星凌 @ 2020-06-17 19:38:45
@Binary_Search_Tree 欧我明白您的意思了
by bellmanford @ 2020-06-17 20:22:55
@Binary_Search_Tree Orz 队爷%%%