我们考虑这个块内部的最大值。不妨将其设置为 mxmxmx,并设置一个区间减的 tagtagtag(因为我们只会将数值减小而不会增大)。
如果 mx≤x×2mx≤x×2mx≤x×2,则我们直接把所有大于 xxx 的数减去 xxx。
如果 mx>x×2mx>x×2mx>x×2,则我们把小于 xxx 的数加上 xxx,并打上区间减的标记。
然后最大值随之更新即可。
这样我们发现,由于最大值与 nnn 同阶,因此一个块内的总复杂度是 O(n)O(n)O(n)。
蒟蒻不太理解题解中这一段,为什么一个块内的总复杂度是 O(n)O(n)O(n)?求一位大佬详细解释以下qwq