关于一类势能 fhq-Treap 合并
查看原帖
关于一类势能 fhq-Treap 合并
320423
s4CRIF1CbUbbL3AtIAly楼主2024/12/19 09:04

众所周知,对于 P9321 一题,直接进行平衡树合并可以做到单次操作均摊 O(log⁡nlog⁡V)O(\log n\log V),证明和实现见 https://codeforces.com/blog/entry/108601。

我现在遇到了一个 VV 非常大但 nn 比较小的情况,具体来说 V=10600V=10^{600} 而 n=13000n=13000。此时如果认为两个值域为 VV 的数的单次比较或加减的时间复杂度均为 O(log⁡V)O(\log V),最初平衡树中只有 nn 个点,这种情况下进行 nn 次题中操作所需的时间复杂度具体为多少?

2024/12/19 09:04
加载中...