题目描述

这是一道线段树经典题。

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

• 对于 $i\in[l,r]$，令 $A_i\leftarrow\min (A_i,x)$ 。

• 对于 $i\in [l,r]$，令 $A_i\leftarrow A_i+x$。

• 求 $\sum_{i=l}^r A_i ​$。

• 求 $\sum_{i=l}^r B_i$。

• 求 $\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

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$，数据保证过程中所有相关数值及输出的绝对值均在 long long 范围内。

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