题解
分块。
先分块,然后对每一个块内排序。
修改时对于处于一个块内的暴力修改后重新排序,对于处于不同块的把最左最右两个不完整的块暴力修改,然后对中间的块打标记。
查询时对整个块直接二分查询,对不完整的块就暴力查询。
时间复杂度:$O(Q\sqrt{N} \log N)$
1 |
|
分块。
先分块,然后对每一个块内排序。
修改时对于处于一个块内的暴力修改后重新排序,对于处于不同块的把最左最右两个不完整的块暴力修改,然后对中间的块打标记。
查询时对整个块直接二分查询,对不完整的块就暴力查询。
时间复杂度:$O(Q\sqrt{N} \log N)$
1 | #include <cstdio> |
v1.5.2