P16702 [MCO 2026] 雨水收集

在 MCO 小镇中，并排矗立着 $N$ 座塔，从左到右第 $i$ 座塔（下标从 $0$ 开始）的初始高度为 $H_i$。一场大雨过后，塔顶可能会积水。MCO 的居民龙 Evirir 想知道这些塔一共能收集多少雨水。 对于一段塔的区间 $[l, r]$（即塔 $l, l+1, \ldots, r$），其降雨量定义如下： - 对于每个塔 $j$，当且仅当存在塔 $i$ 和 $k$，满足 $l \le i \le j \le k \le r$，并且塔 $i$ 与塔 $k$ 都至少比塔 $j$ 高 $x$，即 $$ H_i - H_j \ge x \quad \text{且} \quad H_k - H_j \ge x, $$ 则可以在塔 $j$ 上积起高度为 $x \ge 0$ 的水柱。 - 定义 $f(j)$ 为塔 $j$ 上能够积起的水柱的最大高度。 - 降雨量定义为 $$ f(l) + f(l+1) + \cdots + f(r), $$ 即这些塔上可积起的最大水柱高度之和。 Evirir 对新一代马来西亚 OI 选手充满信心，所以如果只让你求一个区间的降雨量，那就太简单了。相反，你需要处理 $Q$ 个操作，每个操作属于以下两种类型之一： - 更新：$0\ l\ r\ x$ --- 对所有满足 $l \leq i \leq r$ 的 $H_i$ 加上 $x$。 - 询问：$1\ l\ r$ --- 输出塔区间 $[l,r]$ 的降雨量。 注意： - 在回答区间 $[l, r]$ 的询问时，计算 $f(i)$ 和降雨量时不应考虑该区间外的塔。区间外的塔不能用于蓄水。 - 塔的高度可以为负数，但规则保持不变。相关说明可参考样例。

第一行包含两个用空格分隔的整数 $N$ 和 $Q$。 第二行包含 $N$ 个用空格分隔的整数 $H_0, H_1, \ldots, H_{N-1}$。 接下来有 $Q$ 行，每行表示一个操作，包含若干个用空格分隔的整数： - 更新：$0\ l\ r\ x$ --- 对所有满足 $l \le i \le r$ 的 $H_i$ 加上 $x$。 - 询问：$1\ l\ r$ --- 输出塔区间 $[l, r]$ 的降雨量。

对于每个询问，按顺序输出区间 $[l, r]$ 中塔的降雨量，每个答案占一行。

### 提示 $\underline{样例\ 1}$ 该样例适用于子任务 1、5 和 6。 共有 $N = 9$ 座塔。下面是更新与询问的可视化： :::align{center}  ::: 在第一次询问 $\texttt{1 1 6}$ 中，考虑的是第 $1$ 到第 $6$ 座塔。来看高度为 $1$ 的塔 $j = 5$。塔 $5$ 上可以积起高度为 $1$ 的水柱，因为： - 塔 $i = 3$ 的高度为 $3$，比塔 $5$ 高 $2$。 - 塔 $k = 6$ 的高度为 $2$，比塔 $5$ 高 $1$。 但塔 $5$ 上不能积起高度为 $2$ 的水柱，因为不存在满足 $j \le k \le 6$ 的塔 $k$，其高度至少比塔 $5$ 高 $2$（即高度至少为 $1 + 2 = 3$）。注意，不能取 $k = 7$，因为 $k$ 不在此次询问的区间 $[1, 6]$ 内。因此，$f(5) = 1$，这由塔 $5$ 上的 $1$ 个水格表示。 在第二次询问 $\texttt{1 0 8}$ 中，考虑的是第 $0$ 到第 $8$ 座塔。来看高度为 $-1$ 的塔 $j = 4$。塔 $4$ 上可以积起高度为 $6$ 的水柱，因为塔 $i = 0$ 和塔 $k = 7$ 的高度都为 $5$，都比塔 $4$ 高 $6$。同时也可以证明，$6$ 已经是可能的最大高度，因此 $f(4) = 6$。 在更新 $\texttt{0 1 4 2}$ 中，第 $1$ 到第 $4$ 座塔的高度都增加了 $2$。在更新 $\texttt{0 6 8 -4}$ 中，第 $6$ 到第 $8$ 座塔的高度都减少了 $4$。 在询问 $\texttt{1 6 6}$ 中，请注意：即使一座塔的高度为负数，它仍然需要周围有更高的塔才能蓄水。 注意，通过取 $i = j = k$，总是可以在一座塔上积起至少高度为 $0$ 的水柱。 $\underline{样例\ 2}$ 该样例适用于子任务 1、5 和 6。 ### 评分 对于所有测试用例，输入满足以下限制： - $1 \le N\leq 5 \cdot 10^6$ - $1 \le Q \leq 5 \cdot 10^4$ - 对所有 $0 \le i \le N - 1$，有 $|H_i| \leq 10^7$ - 对所有更新和询问，都有 $0 \le l \le r \le N - 1$ - 对所有更新，都有 $|x| \leq 10^7$ - 至少有一个操作是询问。 | 子任务 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $8$ | $N, Q \leq 1000$ | | $2$ | $8$ | $Q = 1$ | | $3$ | $16$ | $N \leq 10^6$ 且输入中没有更新操作 | | $4$ | $18$ | 更新中 $l = r$ 和 $x > 0$，且询问中 $[l, r] = [0, N - 1]$ | | $5$ | $25$ | $N \leq 5 \cdot 10^5$ | | $6$ | $25$ | --- |