P1004：区间增加、区间 chmin、区间最大值、区间和

题目描述

给定一个长度为 $n$ 的数组 $a$，实现支持以下四种操作的结构

1. 操作 $0\ l\ r\ x$ : 把 $[l,r]$ 范围的每个数，增加 $x$
2. 操作 $1\ l\ r\ x$ : 把 $[l,r]$ 范围的每个数 $v$，更新成 $\min(v, x)$
3. 操作 $2\ l\ r$ : 查询 $\max \limits_{i=l}^r a_i$
4. 操作 $3\ l\ r$ : 查询 $\sum \limits_{i=l}^r a_i$

输入输出格式

输入

第一行输入两个整数 $N$ 和 $Q$。

第二行输入 $N$ 个整数表示数组 $a$ 的初始值

接下来 $Q$ 行，每行表示一个操作，格式如下：

• $0\ l\ r\ x$ （对应加操作）
• $1\ l\ r\ x$ （对应赋值操作）
• $2\ l\ r$ （对应 $\max$ 查询）
• $3\ l\ r$ （对应 $\sum$ 查询）

其中 $1 \le l \le r \le N$

输出

对于每一次查询操作，输出一个整数作为结果。

样例

5 7
1 2 3 4 5
0 1 3 4
1 4 5 2
2 1 5
3 2 4
1 2 5 3
2 1 5
3 1 5

7
15
5
15

数据范围

$1 \le N,Q \le 2\times 10^5$, $-10^9 \le a_i \le 10^9$