随记 – 一月十八日 – 关于分块

终于体会到了“看了题解都可能写不出来”的绝望了——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$代表区间长。

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

回到原题。我们考虑采取重链剖分使得整棵树划分成序列区间，由此每一个查询都可以转化为：在节点$u$发生状态更改后，其到根节点的路径上所有点的增广权值$\pm 1$，问操作完成后权值为负的节点数量。实在没有什么高级数据结构能够胜任这项工作。我考虑过线段树，这样似乎只用维护$-1, 0$的个数以计算答案的变化量，但由于是区间减法，故实际上还要想办法维护权值为$1, 2, 3, \dots$的节点个数，几乎不可能实现。

但假如我们应用上文提及的分块后使序列部分有序的思想，由于整个区间都有变化量为$\pm 1$，故操作后整块仍然有序，可以二分每一块内的答案。对于不足整块的部分，我们暴力修改即可。此时已经比暴力$\mathrm{O}(n^2)$更优，但仍难以通过本题。我们加入以下几个优化：

• 每一条重链的链长是不同的。对每条链采取不同的块长。
• 注意到每次对单块的答案的修改为$1$，所以我们直接在上一次答案的基础上暴力移动。
  • 同时为了保证暴力移动的时间复杂度，可以将每一块中元素大小相同的缩成一个点。
• 对不足整块的部分，暴力修改元素后不重新全部排序。我们把应该修改的元素缓存下来，修改后它们仍然有序，直接和未修改的元素归并即可。

这样，时间复杂度可以降到$\mathrm{O}(n\sqrt{n})$。更详细的题解