@[夏色祭Official](/user/361559) ???路径压缩是优化呀
by Tony2 @ 2020-08-10 13:32:45
@[Tony2](/user/171288) 带路径压缩肯定不能撤销，不能撤销就只能从上一层继承并查集了，但是这个开销太大了...
by 夏色祭Official @ 2020-08-10 13:34:18
@[夏色祭Official](/user/361559) 上一层是什么意思？还有你可以参考一下我并查集的代码
by Tony2 @ 2020-08-10 13:38:42
@[Tony2](/user/171288) 线段树分治上维护数据结构有两个思路，一个是利用操作序变成树上dfs序也就是栈序，使用可撤销数据结构；另一个是利用树深度有限多次复用数据结构，具体来说就是维护 log 个数据结构，每次往下走都从父亲那里拷贝一份过来
by 夏色祭Official @ 2020-08-10 13:43:41
比如并查集一般使用撤销，线性基一般就复用
by 夏色祭Official @ 2020-08-10 13:44:23
@[夏色祭Official](/user/361559) 我应该是撤销，就是重复上次的操作以复原
by Tony2 @ 2020-08-10 13:45:32
是的，如果撤销的话就必不能路径压缩，但是复用并查集代价太大了，所以这题大概没法路径压缩
by 夏色祭Official @ 2020-08-10 13:46:08
@[夏色祭Official](/user/361559) u1s1，是 $O(m(1+\log_{2+m/n} n))$
by derta @ 2022-08-25 20:22:45