题解：P13977 数列分块入门 2

Jadonyzx · 2025-09-06 07:47:22 · 题解

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

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

考虑如何修改。

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