2259：数组-2

上题中（数组-1）著名波普艺术家在大脑中随机生成了一个长度为 n 的数组 A，但因为无法完整恢复数据，所以他决定放弃恢复，接着清空了大脑，他想请你帮他重新创造一个数组。

清空大脑意味着初始状态数组内数据全为 0 ，他有三种操作：

C 操作：对数组 A 的 [L,R] 区间内的每个单元加上一个整数 NUM；

X 操作：对数组 A 的 [L,R] 区间内的每个单元加上该区间内的最大值 MAX；

N 操作：对数组 A 的 [L,R] 区间内的每个单元减去该区间内的最小值 MIN。

在过程中他还会不断询问，你需要告诉他数组 A 的 [L,R] 区间所有数的和。

输入两个整数 n 和 m，分别为数组长度，操作和询问次数的总和。

接下来是 m 行

如果第一个字符为 C，接下来三个整数 L , R , NUM，表示对 [L,R] 区间内的所有数加 NUM；

如果第一个字符为 X，接下来两个整数 L , R，表示对 [L,R] 区间内的所有数加上 [L,R] 区间内的最大值 MAX；

如果第一个字符为 N，接下来两个整数 L , R，表示对 [L,R] 区间内的所有数减去 [L,R] 区间内的最小值 MIN；

如果第一个字符为 Q，接下来两个整数 L , R，表示询问 [L,R] 区间内的所有数的和。

其中 1 ≤ n,m ≤ 1e5，1 ≤ NUM ≤ 10，且保证数组每个单元的数据和每次询问的结果都不超过 int 的范围。

对于每个询问 Q，你需要给出答案，一行输出一个答案，最后一个答案后也需换行。

10 9
C 1 10 5
Q 4 4
C 3 6 3
X 1 10
Q 1 10
N 1 5
Q 2 4
C 2 4 1
Q 2 4

5
142
6
9
 

线段树

第七届编程大赛-热身赛