题解：P13978 数列分块入门 3

Jadonyzx · 2025-09-06 07:50:01 · 题解

分块，然后考虑怎么查询整块的。

我们不妨将每块的元素提前排好序，查询的时候二分当前块中第一个小于等于 x 的元素，二分是 O(\log) 的，而最多跳 O(\sqrt n) 个块，一共查询 n 次，查询总复杂度 O(n\sqrt n \log n)。

考虑如何修改。

如果整块都加，直接打一个标记即可，否则直接整体重构，复杂度同上。