很有意思的题，数据结构不是重点，重点在于对问题的观察与简化。

首先注意到每个点之间的操作相对独立，最后也只求每个单点的答案。所以考虑把操作离线下来，在序列上扫描线， 时刻加入一个操作， 时刻删去一个操作。扫描时开一棵时间轴线段树，位置 存储这个时刻的增加量 。

于是问题变成了，对 个不同的限制 和操作序列 求操作完之后的值。(方便起见，在所有操作前设一个 )

注意到这题麻烦之处在于有两个界限制着操作过程中的值。如果只有一个界，假设这个界是对 取 ，那是比较容易做的，答案就是 。设 为 序列的前缀和，答案就是 。如果只有一个对 取 的界，答案也可以类似计算。

我们考虑找到一个时刻 ，使得 处的值容易确定，且 后面只会碰到一个界。容易发现，如果一段时间中 的极差大于等于 ，设 表示 在其中取最大值的位置， 表示 在其中取最小值的位置，那么 时刻一定会碰到一个界。

于是我们二分找到极差 的最短后缀，求出其中 最大值和最小值的位置 ，如果 ，那么在 时刻当前值一定为 ，最终值一定就是 。否则就是 。当然还有找不到这种后缀的情况，那说明整个过程中都碰不到上界，答案也容易计算。

时间复杂度为 。