题目描述

在 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]$ 中塔的降雨量，每个答案占一行。

9 7
5 3 1 3 -1 1 2 5 3
1 1 6
1 0 8
0 1 4 2
0 6 8 -4
1 1 6
1 3 6
1 6 6

6
21
2
0
0

5 6
-2 3 1 4 2
0 0 2 1
0 0 4 3
0 3 4 8
0 0 0 10
0 1 3 1
1 0 4

10

提示

提示

$\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$		$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$		---