自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:31:28，当前版本为作者最后更新于2025-01-13 17:14:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

cnblogs。

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

给定长度为 $n$ 的数组和 $q$ 次操作，每次操作如下：

• 给数组一个位置加 $v$。
• 给定不超过 $k$ 个位置，要求在数组这些位置的总和超过 $v$ 的时候输出该操作的编号。

这题就是 $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)$。

轻松拿下目前最优解。