复杂度证明求助
查看原帖
复杂度证明求助
350880
MaxBlazeResFire楼主2023/8/27 14:02

按题解的做法,维护一个等价类线性基栈,对于每个 11 维护等价类合并。

那这样的话感觉合并次数级别是不是 O(n)O(n),每次合并 O(log⁡2V)O(\log^2V),怎么做到题解里说的均摊 O(nlog⁡V)O(n\log V)?

望证明,谢谢!(或者是有更优的写法但我不知道)

2023/8/27 14:02
加载中...