P8937 [JRKSJ R7] 铃音的第二分块 题解

· · 题解

upd: 之前提交记录里的代码好像有 > 写了个 \ge 但是通过题目了，现在链接里的代码应该是正确的。

是一道不错的套路题，下文中为了方便书写认为 nq 同阶，该做法与官方题解不太相同。

对于操作 1，我们发现如下性质：

  1. 对于 [1,x]\cup(2x,\inf] 中的数，他们的相对顺序不变；
  2. 对于 (x,2x] 中的数，他们经过这次操作后它们至少减半，也就是说该类型的操作不会超过 O(n \log V) 次。

一个粗糙的做法：

考虑每 B 个数分一块，每个块中用平衡树维护，每次修改对于第二部分的数直接暴力取出重新插入回平衡树，复杂度 O(n\log V\log n)；对于第一部分的数因为相对顺序不变，所以不会改变平衡树形态，可以直接打区间减标记，对于小块则直接将平衡树转化为排序后的序列，然后归并排序，然后再建树，复杂度 O(B+\dfrac n B \log n)。

取 B = \sqrt{n \log n} 即可取到最优复杂度 O(n\sqrt{n\log n} + n \log V \log n)。

但是因为平衡树常数太大，即使是在 20\text s 的时限下也不足通过。

一个精细的做法：

考虑尝试使用树状数组代替平衡树，首先你要会树状树组的线性建立和转化为前缀和数组的形式的方法，然后我们可以使用树状数组维护每一块排序后的差分，那么查询可以和修改的第一部分可以对于整块树状树组上二分，对于小块把树状树组拍回排序后的数组解决问题的。

考虑如何处理修改的第二部分，树状树组不支持删除，所以对每一块我们再开一个大小为 s 缓存，每次删除数的时候，就先找到对应要删除的区间 (x,2x]，然后把该值域中的数先取出至缓存中，然后都变为 x，并且打上代表已经消失了的标记。

对于缓存中的数，因为其总量不会超过 O(\dfrac{ns}B) 个，所以可以暴力做修改与查询，当缓存中的数超过 s 时，则将缓存与块重构。

现在分析时间复杂度，重构可以用树状树组的线性建立，而重构次数是 O(n+\dfrac{n\log V}s) 其中 O(n) 来源于散块修改，重构复杂度是 O(B) 的；查询复杂度是 O(\dfrac n B \log n + \dfrac n Bs) 的；修改复杂度是类型一 O(\dfrac n B s + \dfrac n B \log n)，类型 2 每个数不会超过 O(n \log V) 次，每次至多会推平额外 O(s) 个数，单点复杂度树状树组是 O(\log n) 的，因此复杂度是 O(ns \log V \log n) 的（当然也可以做到 O(n\log V\log n)，但由于实际测试中要多一些判断导致其甚至跑不过该复杂度，因此在下文提及），取 s = O(\log n), B = O(\sqrt{n\log n})。

时间复杂度 O(n \sqrt {n \log n} + n \log^2n \log V)，但是由于最后的三个 \log 常数都非常非常小，因此可以通过。

由于时间比较紧，所以如果被卡常了加一些剪枝即可通过。

code

接下来写一下如何把 O(n \log^2 n \log V) 做法变为 O(n \log n \log V)，你发现额外的缓存中的 s 个数实际上只有相邻前后不再缓存里才有意义，于是你修改操作 2 的时候，在树状树组上可以跳过那些前后都在缓存里的更新的差分（因为本质上没更新），这样复杂度就做到了 O(n \log n\log V + n \sqrt{n \log n})。