刚学OI,萌新求助
查看原帖
刚学OI,萌新求助
96197
Minuses楼主2020/10/15 20:25

这题纯按秩合并/启发式合并复杂度是对的嘛?

就是首先先按秩合并/启发式合并一下,然后把询问暴力合并,再暴力找对应点。

这样复杂度本蒟蒻觉得是 Θ(\Theta(询问次数logN)logN)的,然而询问次数好像无法保证所以复杂度似乎也无法保证?

但是题解确实有人使用按秩合并/启发式合并/按答案size合并等等方法过掉了这个题。

令本蒟蒻十分困扰

望大佬解答/kk

2020/10/15 20:25
加载中...