Luogu7447 [Ynoi2007] rgxsxrs

题意：给定一个长为 的序列 ，进行 次操作：

• 将区间 中所有 的元素减去 。

• 表示询问区间 的和，最小值，最大值。

，，时限 ，空限 。

---

我们认为 。

考虑倍增分块，倍数为 ，将值域分为形如 的 个块。

对于每个块内的数，分别用线段树维护。需要维护区间最小值最大值以及和。

对第 棵线段树修改时，分三类讨论：

• ① ：操作没有影响，直接返回。

• ② ：区间内减 后仍然都在当前块内，打区间减标记即可。

• ③ 对于叶节点，：将其删除，加入下一层。

三类位置形成若干连续段，若段数为 ，则本次操作的复杂度为 。

在 ③ 中，每个值只会下降 次，这部分复杂度为 。

其余的复杂度可以看做与 ② 的个数直接相关。

块内的总和至多是 的，每次修改中，若存在 ① 且 ② 生效 次，则总和至少减少 。

于是花费于 ② 的总复杂度是 的。

选取一个合适的 可以做到 。

此时空间复杂度是 ，且常数较大，难以通过。

底层进行 分块，对小区间进行暴力，即可改进为 。