7110: 线段树经典题
[Creator : ]
Description
这是一道线段树经典题。
你需要写一个数据结构（线段树）维护长度为 n 的三个序列 A,B,C，下标为 $1\sim n$，支持：
初始给定 $A_i$，同时初始 $B_i=0,C_i=A_i$。
你需要写一个数据结构（线段树）维护长度为 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$。
初始给定 $A_i$，同时初始 $B_i=0,C_i=A_i$。
Input
第一行两个正整数 n,Q，分别表示序列长度和操作个数。
第二行 n 个整数表示序列 $A_i$。
接下来 Q 行，每行第一个整数表示操作类型编号，其他数字意义同题面：
第二行 n 个整数表示序列 $A_i$。
接下来 Q 行，每行第一个整数表示操作类型编号，其他数字意义同题面：
- 若为类型 1，接下来三个整数 l,r,x。
- 若为类型 2，接下来三个整数 l,r,x。
- 若为类型 3，接下来两个整数 l,r。
- 若为类型 4，接下来两个整数 l,r。
- 若为类型 5，接下来两个整数 l,r。
Output
对于每个类型为 3,4,5 的操作，输出一行一个整数表示答案。
Constraints
对于 $100\%$ 的数据，$1\leq n,Q\leq 2\times 10^5,|a_i|\leq 10^9，1\leq l\leq r\leq n$，数据保证过程中所有相关数值及输出的绝对值均在 long long 范围内。
Sample 1 Input
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
Sample 1 Output
11
5
16
7
22
10
Sample 2 Input
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
Sample 2 Output
0
-40
3
-27
-40
3