P17826 [COCI 2026/2027 #1] 水 / Voda

Marko 在院子里用木柱搭建了一个**柱状图**：$n$ 根宽度为 $1$ 的柱子紧挨着排列，第 $i$ 个位置的柱子高度为 $h_i$。Marko 喜欢修改自己的作品，因此有时会升高、降低或替换其中的一些柱子。 有时，Marko 只观察**柱状图的一部分**，即位置从 $l$ 到 $r$ 的柱子，并想象有大量雨水落在这些柱子上。此时，观察范围之外的柱子视为**不存在**，因此水可以从第 $l$ 根柱子的左边界和第 $r$ 根柱子的右边界流走。雨会一直下，直到柱状图蓄满水：被两侧较高柱子挡住的水会留下，其余的水全部流走。一个装满水的 $1\times 1$ 方格所容纳的水量为 **$1$ 单位**。 如果一根柱子的顶部上方有水，就称这根柱子**完全被水淹没**。如果柱子的顶部是干燥的，也就是说顶部上方没有水，就称它**没有完全被水淹没**。水仍然可以从侧面接触这样的柱子，水面最高可以与柱顶齐平。 Marko 将依次进行 $q$ 个事件，每个事件属于以下五种类型之一： - `1 i x`：将第 $i$ 根柱子的高度改为 $x$。 - `2 l r x`：将第 $l$ 根到第 $r$ 根柱子的高度全部改为 $x$。 - `3 l r x`：将第 $l$ 根到第 $r$ 根柱子的高度全部增加 $x$（$x$ 也可以为负数）。 - `4 l r`：Marko 观察第 $l$ 根到第 $r$ 根柱子，询问其中有多少根柱子**没有完全被水淹没**。 - `5 l r`：Marko 观察第 $l$ 根到第 $r$ 根柱子，询问这些柱子**总共能蓄积多少单位的水**。 请帮助 Marko 回答所有询问。观察不会改变柱状图，每次询问结束后，水都会消失。

第一行包含两个正整数 $n$ 和 $q$（$1\le n,q\le 200\,000$），分别表示柱子的数量和事件的数量。 第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$0\le h_i\le 10^9$），表示各根柱子的初始高度。 接下来 $q$ 行，每行以上述格式之一描述一个事件。满足 $1\le i\le n$，$1\le l\le r\le n$。对于类型 $1$ 和类型 $2$ 的事件，$0\le x\le 10^9$；对于类型 $3$ 的事件，$-10^9\le x\le 10^9$。 保证在任何时刻，所有柱子的高度都是 $0$ 到 $10^9$ 之间的整数。

对于每个类型 $4$ 或类型 $5$ 的事件，按照它们在输入中出现的顺序，各用一行输出该询问的答案。

### 样例 1 解释 柱状图的高度为 $[3,0,2,4,1,4,0,2]$。第一次询问中，Marko 观察整个柱状图。第 $2$、$3$、$5$、$7$ 根柱子上方分别蓄有 $3$、$1$、$3$、$2$ 单位的水，而第 $1$、$4$、$6$、$8$ 根柱子的顶部是干燥的。这四根柱子没有完全被水淹没，所以答案为 $4$。 第二次询问中，Marko 观察的柱子高度为 $[0,2,4,1]$。高度先上升再下降，因此所有水都会从左边界或右边界流走。没有柱子完全被水淹没，答案为 $4$。 ### 样例 2 解释 柱状图的高度为 $[5,1,3,2,4,1]$。当 Marko 观察整个柱状图时，第 $1$ 根和第 $5$ 根柱子之间的水面高度为 $4$，而第 $5$ 根柱子右侧的水会全部流走。因此，各根柱子上方分别蓄有 $0,3,1,2,0,0$ 单位的水，总计 $6$ 单位。第 $2$、$3$、$4$ 根柱子完全被水淹没，其余三根没有，所以第二次询问的答案为 $3$。 ### 评分与子任务 | 子任务 | 分值 | 附加限制 | | --- | --- | --- | | 1 | 21 | $n,q\le 5000$。 | | 2 | 16 | 只有类型 $4$ 的事件。 | | 3 | 11 | 只有类型 $4$ 和 $5$ 的事件。 | | 4 | 13 | 只有类型 $1$ 和 $4$ 的事件。 | | 5 | 14 | 只有类型 $1$、$4$ 和 $5$ 的事件。 | | 6 | 16 | 只有类型 $1$、$2$、$3$ 和 $4$ 的事件。 | | 7 | 19 | 无附加限制。 |