题目描述

这是一道线段树经典题。

你需要写一个数据结构（线段树）维护长度为 $n$ 的三个序列 $A,B,C$，下标为 $1\sim n$，支持以下操作：

1. 对于 $i\in[l,r]$，令 $A_i \leftarrow \min(A_i, x)$。
2. 对于 $i\in[l,r]$，令 $A_i \leftarrow A_i + x$。
3. 求 $\sum_{i=l}^r A_i$。
4. 求 $\sum_{i=l}^r B_i$。
5. 求 $\max_{i=l}^r C_i$。

每次执行前两种修改操作后，需同步更新：$B_i \leftarrow B_i + A_i$，$C_i \leftarrow \max(C_i, A_i)$。

初始条件：给定 $A_i$，且初始 $B_i=0$，$C_i=A_i$。

输入格式

第一行两个正整数 $n, Q$，分别表示序列长度和操作个数。

第二行 $n$ 个整数表示 $A_i$。

接下来 $Q$ 行，每行第一个整数表示操作类型编号，其他数字意义同题面：

• 若为类型 $1$，接下来三个整数 $l,r,x$；
• 若为类型 $2$，接下来三个整数 $l,r,x$；
• 若为类型 $3$，接下来两个整数 $l,r$；
• 若为类型 $4$，接下来两个整数 $l,r$；
• 若为类型 $5$，接下来两个整数 $l,r$。

输出格式

对于每个类型为 $3,4,5$ 的操作，输出一行一个整数表示答案。

样例 1

输入：

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

输出：

11
5
16
7
22
10

样例 2

输入：

10 10
3 -5 -2 -2 3 -1 -1 3 -4 -4
4 5 8
2 1 10 -5
3 1 7
1 8 9 -3
5 1 10
3 7 10
2 2 4 -4
4 1 2
5 8 8
1 2 8 1

输出：

0
-40
3
-27
-40
3

数据范围与提示

对于 $100\%$ 的数据，$1\leq n,Q\leq 2\times 10^5$，$|a_i|\leq 10^9$，$1\leq l\leq r\leq n$。数据保证过程中所有相关数值及输出的绝对值均在 $\text{long long}$ 范围内。

数据均为随机，但没有梯度。