#216691. [MCO 2026] 雨水收集

在 MCO 小镇中，并排矗立着 座塔，从左到右第 座塔（下标从 开始）的初始高度为 。一场大雨过后，塔顶可能会积水。MCO 的居民龙 Evirir 想知道这些塔一共能收集多少雨水。

对于一段塔的区间 （即塔 ），其降雨量定义如下：

• 对于每个塔 ，当且仅当存在塔 和 ，满足 ，并且塔 与塔 都至少比塔 高 ，即
  则可以在塔 上积起高度为 的水柱。
• 定义 为塔 上能够积起的水柱的最大高度。
• 降雨量定义为
  即这些塔上可积起的最大水柱高度之和。

Evirir 对新一代马来西亚 OI 选手充满信心，所以如果只让你求一个区间的降雨量，那就太简单了。相反，你需要处理 个操作，每个操作属于以下两种类型之一：

• 更新： --- 对所有满足 的 加上 。
• 询问： --- 输出塔区间 的降雨量。

注意：

• 在回答区间 的询问时，计算 和降雨量时不应考虑该区间外的塔。区间外的塔不能用于蓄水。
• 塔的高度可以为负数，但规则保持不变。相关说明可参考样例。

第一行包含两个用空格分隔的整数 和 。

第二行包含 个用空格分隔的整数 。

接下来有 行，每行表示一个操作，包含若干个用空格分隔的整数：

• 更新： --- 对所有满足 的 加上 。
• 询问： --- 输出塔区间 的降雨量。

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

样例输入 1

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

样例输出 1

6
21
2
0
0

样例输入 2

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

样例输出 2

10

提示

该样例适用于子任务 1、5 和 6。

共有 座塔。下面是更新与询问的可视化：

:::align{center} :::

在第一次询问 中，考虑的是第 到第 座塔。来看高度为 的塔 。塔 上可以积起高度为 的水柱，因为：

• 塔 的高度为 ，比塔 高 。
• 塔 的高度为 ，比塔 高 。 但塔 上不能积起高度为 的水柱，因为不存在满足 的塔 ，其高度至少比塔 高 （即高度至少为 ）。注意，不能取 ，因为 不在此次询问的区间 内。因此，，这由塔 上的 个水格表示。

在第二次询问 中，考虑的是第 到第 座塔。来看高度为 的塔 。塔 上可以积起高度为 的水柱，因为塔 和塔 的高度都为 ，都比塔 高 。同时也可以证明， 已经是可能的最大高度，因此 。

在更新 中，第 到第 座塔的高度都增加了 。在更新 中，第 到第 座塔的高度都减少了 。

在询问 中，请注意：即使一座塔的高度为负数，它仍然需要周围有更高的塔才能蓄水。

注意，通过取 ，总是可以在一座塔上积起至少高度为 的水柱。

该样例适用于子任务 1、5 和 6。

评分

对于所有测试用例，输入满足以下限制：

• 对所有 ，有
• 对所有更新和询问，都有
• 对所有更新，都有
• 至少有一个操作是询问。