有 \(n\) 个数，给定 \(a_i\) 的初始值以及 \(m_i, v_i\)，每一秒 \(a_i = \min(m_i, a_i + v_i)\)。有 \(T\) 组询问，每次给定
t, l, r，求出第 \(t\) 秒时 \(\sum \limits_{i= l}^r a_i\)，再将 \(a_l \sim a_r\) 赋成 \(0\)。保证 \(t\) 单调递增。\(n, T \le 10^5\)
标签
ODT，主席树我们发现有一个非常难搞的事情是，每个数上次被赋 \(0\) 的时间 \(lst_i\) 参差不齐，很难算出一个数什么时候到达 \(m_i\)。
但是，我们可以暴力维护 \(lst\) 相同的极长段，也就是 ODT。对于这一段，\(lst\) 是相同的，那么每个数都有 \(k = t - lst\) 的时间增长，对于这段数，如果 \(v_ik \ge m_i\)，即 \(\frac{m_i}{v_i} \le k\)，那么得到的 \(a_i\) 为 \(m\)，否则为 \(v_ik\)。使用主席树求出两部分的和即可。
单独处理一下最开始的 \(a_i\) 与 \(v_i = 0\) 的情况即可。
时间复杂度：\(O((n + m) \log (n + m))\)。
通过颜色段均摊的方式，消除不同 \(lst\) 的影响，从而简化问题，算一个经典套路了。