题目其实就是求 \(\sum_{i=L}^Rmax_{j=i-T}^i\space a_i\)
首先，我们只需要维护在 \(t\) 时刻的 \(a_i\) 相对于最初的 \(a_i\) 的增量 \(val_i\) 就可以了。
令 \(l_i\) 表示在 \(i\) 左边第一个 \(j\) 满足 \(a_j>a_i\)，\(r_i\) 表示在 \(i\) 右边第一个 \(j\) 满足 \(a_j>a_i\)。
然后我们用 \(a_{l_i}-a_i\) 来贡献 \(val_j\space\space\space j\in[i,r_i)\)。
画出坐标轴，坐标轴横坐标表示下标 \(i\)，纵坐标表示时刻 \(t\)。那么上述操作就是对所有 \((x,y)\) 满足 \(x\ge i\) 并且 \(y\ge x-l_i\) 的部分加上 \(a_{l_i}-a_i\)。这样的修改的被修改区域的形状是直角梯形，我们可以转换成两个三角形的差。于是我们只需维护这样的操作：给定 \(a\)、\(b\)、\(c\)，然后对所有满足 \(x\ge a\) 且 \(y\ge x-b\) 的 \((x,y)\) 加上 \(c\) 的贡献。
之后我们考虑这样的一个修改会对差分后的询问的贡献。
假设当前的询问为 \((t,p)\) 。
- 如果 \(p\) 在 三角形区域左侧，贡献为 \(0\)，也可以认为是 \(c\times(p-p)\)
- 如果 \(p\) 在三角形区域内部，贡献为 \(c\times(p-(a-1))\)
- 如果 \(p\) 在三角形区域右侧，贡献为 \(c\times((t+b)-(a-1))\)
总的来说，贡献就是 \(c\times (min\{p,t+b\}-min\{p,a-1\})\) 也就是 \(c\times (-min\{p,a-1\}+min\{p-t,b\}+t)\)，这样，就不存在一个修改是否能贡献这一个询问的限制了。