数据结构笔记

分块，为你我陷入疯狂！

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})$)

---