1200:数组-2

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

上题中(数组-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
HINT

线段树

来源
第七届编程大赛热身赛