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)。
轻松拿下目前最优解。