先用set套区间处理所有询问。set里每个元素是一个区间，且它们上次被清零的时间相同。遇到一个操作之后先把 \( l-1 \) 和 \( l \) 之间、 \( r \) 和 \( r+1 \) 之间切断，然后把询问覆盖的区间逐个删除，再扔一个区间进去。set里面初始时每个位置是一个单独的区间。删除区间时，如果区间长度为 \( 1 \) 且是首次被操作，就直接计算它对答案的贡献，否则得到一个 \( (l,r,t,i) \) 的四元组，表示“ \( l \) 到 \( r \) 上次被清空后经过 \( t \) 秒增长再次被清空，答案贡献给第 \( i \) 次操作”。这样的四元组至多 \( 3m \) 个。

然后把 \( (l,r,t,i) \) 四元组按 \( t \) 递增排序，把 \( 1\sim n \) 所有位置按从空变满的时间 \( m_i/r_i \) 递增排序。逐个枚举四元组时维护两个树状数组，一个维护 \( m_i/r_i\leq t \) 的位置的 \( m_i \) 区间和，另一个维护 \( m_i/r_i\gt t \) 的 \( r_i \) 区间和，于是就可以查询每个四元组对答案的贡献了。

时间复杂度 \( O((n+m)\log n) \) 。

（7年前我按照这个算法写的，WA飞了，至今不知哪里写挂，也懒得调。今天突然翻到这题，写了20分钟，一发提交就AC了。这么看来，当年我还是太菜了。）

没有标程？

一个序列，第\(i\)个位置有权值\(w_i\)和属性\(a_i,b_i\)，每过一秒，\(w_i:=\min(w_i+a_i,b_i).\)

\(m\)次操作，在\(t\)时刻询问\([l,r]\)的权值和并将\([l,r]\)的权值清零。

用分块维护这个事情，设块长为\(B\)。查询散块直接暴力，考虑如何快速查询整块。我们要利用\(a_i,b_i\)不会改变的性质。

• 若块内元素在上一次对这个块的操作结束后有数字非0，同样暴力求这个块的答案并将所有元素清零。（复杂度将在之后分析）
• 否则，对于位置\(i\),对于两次操作的时间差\(t\),若\(t\ge \lceil\frac{b_i}{a_i}\rceil\) （\(a_i=0\)的特殊处理掉就好了，不难）则权值为\(b_i\),否则为\(t\cdot a_i\).预处理元素按\(\lceil\frac{b_i}{a_i}\rceil\)排序的结果，那么二分找到一个位置\(pos\),预处理\(pos\)左侧的元素的\(\sum b_i\),右侧元素的\(\sum a_i\)即可。

现在分析一下复杂度。第二种情况对每个块是严格\(O(\log B)\)的。第一种情况只会在这个块被暴力重构后（或开始时）发生一次，所以\(m\)次询问总复杂度是\(O(mB)\).暴力一个块的复杂度是\(O(B)\) （排序在一开始进行一次即可）

总复杂度\(O(n\log n+mB+m\frac{n}B\log B)\),取\(B=\sqrt {n\log n}\)时理论最优，为\(O(m\sqrt {n\log n})\)。

理论上可以离线询问然后将涉及的\(t\)一起排序可以做到\(O((n+m)\sqrt n)\).

这个= =是数据太强了么<。<全都T掉了 没有一个A的