分块

终于体会到了“看了题解都可能写不出来”的绝望了——CF925E May Holidays。

自以为已经对“分块”的思想有了一定掌握，到头来发现自己还只会最基本的、应用最广泛的值域分块。只是题见得不够多罢了。

考虑一种实际操作中不会使用的求区间第$k$大的算法。设块长为$S$，我们将序列分成$\mathrm{O}(\dfrac{n}{S})$块，每一块内直接对元素排序。对于一个询问$[l, r]$，我们二分答案。猜测答案为$d$，在中间的每一整块内二分出$\leq d$的元素数量，两侧暴力查找。这样的复杂度是$\mathrm{O}(\dfrac{len}{S} \log^2 n+S \log n)$的，其中$len$代表区间长。

这告诉我们，分块的目的不仅可以让较大的值域范围内的统计变得更高效，还可以使得元素（部分）有序，适用范围更加广泛。就连分块这种暴力数据结构使用时都需灵活变通，其他算法又何尝不是如此。

（更多…）