5957: 进阶2.5.1 简单的整数问题-2
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：48
解决：36
题目描述
有N个整数A1，A2,....AN,需要对其进行两种操作，一种操作是对给定区间中的每一个数都添加一个给定的数，另一个操作是查询给定区间中数的总和。
输入
第1行包含两个数N和Q（1<=N,Q<=1e5）;第2行包含N个数，为A1A2....AN的初始值（-1e9<=Ai<=1e9）；
接下来Q行，每行表示一种操作，“C a b c”表示将Aa,Aa+1，...，Ab中的每个数都加c（-1e4<=c<=1e4），“Q a b”表示查询Aa,Aa+1,...Ab的总和。
接下来Q行，每行表示一种操作，“C a b c”表示将Aa,Aa+1，...，Ab中的每个数都加c（-1e4<=c<=1e4），“Q a b”表示查询Aa,Aa+1,...Ab的总和。
输出
对每个查询，都单行输出区间和的值。
样例输入 复制
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4样例输出 复制
4
55
9
15提示
总和可能超过32位整数范围。
为区别于简单的整数问题-1（树状数组、线段树），本题建议尝试采用分块算法解决
POJ3468
为区别于简单的整数问题-1（树状数组、线段树），本题建议尝试采用分块算法解决
POJ3468