题解：P7603 [THUPC2021] 鬼街

cnblogs。

我们希望在线解决如下形式的问题：

这题就是 $k = \omega(n)$ 的版本。

众所周知，折半警报器能在均摊做到 $\mathcal O(1) - \mathcal O(k^2\log q\log V)$（$x - y$ 表示操作一复杂度为 $x$，操作二复杂度为 $y$）。但我发现了一个 $\mathcal O(1) - \mathcal O(k\log V)$ 的算法，我们就称其为 "二进制警报器" 吧。

对于一个二操作，设其对应位置为 $pos_1,...,pos_d$。对于该操作，维护一个阈值 $h$，只要 $a_{pos_i}$ 的值经过（$a_x \to a_x+w$ 的时候，我们认为它经过了 $(a_x,a_x+w]$）$2^h$ 的倍数时 "报警"。如果目前的 $h$ 能让所有 $a_{pos_i}$ 在都不报警的前提下总和超过 $v$，那么将 $h$ 降低 $1$。

对于每个 $h=h_0$，报警次数总和是不超过 $\mathcal O(k)$ 的：$h$ 降到 $h_0$ 时，$v - \sum_{i=1}^{k}a_{pos_i}$ 应是 $\mathcal O(k2^{h_0})$ 的；而一个元素报警两次时，它必然增加了至少 $2^{h_0}$。

对每个 $(\text{位置},h)$ 开个 vector 维护警报器并利用二进制优化修改时找报警器的复杂度，复杂度是 $\mathcal O(1) - \mathcal O(k\log V)$。

对于这题，复杂度为 $\mathcal O(n + q\omega(n)\log V)$。

轻松拿下目前最优解。