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

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

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

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