考虑以下问题：
维护一个长度为 \(n\) 的序列，并在线支持 \(q\) 次以下操作：
- 给 \(x\) 个位置加 \(val\)；
- 给定不超过 \(y\) 个位置，在这些位置被加了不少于 \(val\) 时输出编号；
在操作一之后暴力判断询问是否需要回答是不优的，因为会有很多次无效判断，因此高效解决此问题的关键在于怎么快速确定一个询问是否需要判断。
考虑可以用 \((v,S)\) 来表示一个询问，其中 \(v\) 是剩余询问值，\(S\) 是贡献位置集合。一个简单而关键的观察是如果不存在 \(x\in S\)，满足 \(x\) 贡献了 \(\dfrac{v}{|S|}\)，那么询问一定不满足，其充要性容易证明。那么记 \((v,S)\) 这个询问的闸值为 \(\dfrac{v}{|S|}\)，那么在每一个位置维护一个数据结构（通常为堆），每次找到该位置上贡献值已经不少于闸值的询问，然后判断，更新闸值即可。
上述做法的时间复杂度均摊分析可以得到为 \(O(x)-O(y\log q \log V)\)。(\(O(x)-O(y)\) 表示操作一时间复杂度为 \(O(x)\)，操作二时间复杂度为 \(O(y)\))
注意到上述做法的瓶颈在于每次更新闸值时都要把新闸值的询问放入数据结构，太不优秀了。考虑能否优化这一点，考虑将闸值的形式修改一下：我们称 \(x\) 加 \(y\) 时经过了 \((x,x+y]\)。询问 \((v,S)\) 的闸值 \(h\) 为满足 \(S\) 中所有数都不经过 \(2^{h+1}\) 的倍数时，可以加的数总和大于 \(v\) 的数。把询问挂在 \((x,h)(x \in S)\) 上。那么当一个位置 \(i\) 的数经过 \(2^x\) 时，我们判断所有挂在 \((i,x)\) 上的询问是否满足即可，如果需要不需要降闸值，那么所有询问不变；否则添加新询问。
闸值在判断 \(y\) 次后一定下降，因此时间复杂度为 \(O(x+\log V)-O(y\log V)\)。