关于第二分块时间复杂度证明
查看原帖
关于第二分块时间复杂度证明
569235
w9095楼主2024/7/12 22:32

我们考虑这个块内部的最大值。不妨将其设置为 mxmx,并设置一个区间减的 tagtag(因为我们只会将数值减小而不会增大)。

如果 mx≤x×2mx≤x×2,则我们直接把所有大于 xx 的数减去 xx。

如果 mx>x×2mx>x×2,则我们把小于 xx 的数加上 xx,并打上区间减的标记。

然后最大值随之更新即可。

这样我们发现,由于最大值与 nn 同阶,因此一个块内的总复杂度是 O(n)O(n)。

蒟蒻不太理解题解中这一段,为什么一个块内的总复杂度是 O(n)O(n)?求一位大佬详细解释以下qwq

2024/7/12 22:32
加载中...