P2801 教主的魔法 笔记

补补分块笔记，因为分块水平过于低下。

考虑对序列分块，设块长为 $B$，“有多少个数大于某个数”启示二分，因此需要维护每个块内有序。

对于整块，区间加不影响顺序，对每个块开一个 tag 记录加值。对于散块，只能暴力重建块了。

修改时时间复杂度 $O(\frac{N}{B}+B\log B)$，查询时间复杂度 $O(\frac{N\log B}{B}+B)$。两项相加忽略低系数项得 $\frac{N\log B}{B}+B\log B=(1+\log B)(\frac{N}{B}+B)$，当 $B=\sqrt{N}$ 时，得到最优总复杂度 $O(Q\sqrt{N}\log \sqrt{N})$。