辰星凌 @ 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 青君 @ 2020-06-17 17:19:45
@辰星凌
线段树分治套冰茶姬是什么？？
by critnos @ 2020-06-17 17:19:53
/fad
by 辰星凌 @ 2020-06-17 17:20:42
@青君 线段树分治
by 鏡音リン @ 2020-06-17 17:20:57
并查集按size合并理论上也没啥问题吧
by 辰星凌 @ 2020-06-17 17:21:33
@鏡音リン 但是模板题开O2秒过不开O2TLE是什么鬼
by 鏡音リン @ 2020-06-17 17:22:20
@辰星凌 常数写大了，吸氧就好了
by _LiM @ 2020-06-17 17:23:16
size合并复杂度也可以用那套按秩合并方法分析吧，应该是对的
by 辰星凌 @ 2020-06-17 17:23:22
@鏡音リン 不至于吧...一个
by 辰星凌 @ 2020-06-17 17:24:16
艹，加了一句if(x==y)return 就过了
by FZzzz @ 2020-06-17 17:24:31
@辰星凌 怎么会没有常数，我觉得是您写丑了罢（