区间取 min/max/加、区间求和（Range Chmin Chmax Add Range Sum）

问题描述

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。请按顺序处理以下 $Q$ 个查询：

• 0 l r b：对每个 $i = l, l+1, \dots, r-1$，执行 $a_i \leftarrow \min(a_i, b)$。
• 1 l r b：对每个 $i = l, l+1, \dots, r-1$，执行 $a_i \leftarrow \max(a_i, b)$。
• 2 l r b：对每个 $i = l, l+1, \dots, r-1$，执行 $a_i \leftarrow a_i + b$。
• 3 l r：输出 $\sum_{i=l}^{r-1} a_i$。

约束条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $|a_i| \leq 10^{12}$ 在处理查询过程中始终成立
• $0 \leq l < r \leq N$

输入格式

$N\ Q$
$a_0\ \cdots\ a_{N-1}$
$Query_0$
$Query_1$
:
$Query_{Q-1}$

5 7
1 2 3 4 5
3 0 5
2 2 4 100
3 0 3
0 1 3 10
3 2 5
1 2 5 20
3 0 5

15
106
119
147