辰星凌 @ 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 _LiM @ 2020-06-17 17:24:38
提 高 组 初 赛
by FZzzz @ 2020-06-17 17:24:49
哦是写锅了啊（（
by 鏡音リン @ 2020-06-17 17:25:22
没判x==y还行 真就提高组初赛
by 辰星凌 @ 2020-06-17 17:25:34
（捂脸）
by 辰星凌 @ 2020-06-17 17:26:24
因为按深度合并的代码里面没有特判就过了，我以为没有这种数据
by 辰星凌 @ 2020-06-17 17:28:27
淦，那我不特判的代码是咋过的啊
by 青君 @ 2020-06-17 17:28:29
@辰星凌
哦原来这玩意儿叫线段树分治。
记得我唯一一次写这个东西没写路径压缩跟按秩合并还跑得飞快。。
by 辰星凌 @ 2020-06-17 17:28:38
珂怕
by 142857cs @ 2020-06-17 17:32:04
@辰星凌 深度合并也必须特判
by 142857cs @ 2020-06-17 17:32:57
不特判能过是数据水