分块，为你我陷入疯狂！

P2801 教主的魔法

两种操作：

  1. 区间加
  2. 区间查询有多少值大于等于 x

n \leq 10^6,q \leq 3000,x \leq 10^9

没有区间加法的话是一个很简单的二维数点题，加上修改的话可以线段树二分，时间复杂度 O(n \log^2 n)

这个题也可以用分块来完成，

对于查询的操作，小段暴力查询，大段我们考虑块内二分，可以使用 lower_bound，单次操作时间复杂度 O(\sqrt{n}\log{\sqrt{n}})。

为了保证块内有序，对于区间加的操作，小段暴力，大段打 tag，对于小段来说，我们每次对整个块暴力重构排序，时间复杂度为 O(\sqrt{n}\log{\sqrt{n}}+\sqrt{n})

总时间复杂度为 O(q\sqrt{n}\log{\sqrt{n}})，由于 q 与 \sqrt{n} 同阶，所以可以近似看作 O(n \log \sqrt{n})

P5356 Ynoi2017 由乃打扑克

两种操作：

  1. 区间加

  2. 查询区间 [l,r] 的第 k 小值。

1\leq n,m\leq 10^5，-2\times 10^4\leq 每次加上的数和原序列的数 \leq 2\times 10^4。

注意到我们查第 k 小完全可以采用二分，我们对值域进行二分，每次查询一个值在区间内的排名，根据排名与 k 的关系判断范围的改变，这样只要我们找到后继就可以了。

那么判断排名，实际上就是上边那个题所做的工作了，记值域大小为 l，这样我们可以得出查询的时间复杂度为 O(\log l \sqrt{n}\log\sqrt{n})，这边的块长判断比较玄学，我不太会算，有会算的可以教教我（

总时间复杂度为 O(q(\log l \sqrt{n}\log\sqrt{n} + \sqrt{n}\log\sqrt{n}))