A Simple Problem with Integers POJ

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

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

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

题解：注意add也可能超过int

 1 #pragma warning(disable:4996)
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 #define lson root<<1
10 #define rson root<<1|1
11 #define ll long long 
12 
13 const int maxn = 100005;
14 
15 struct node {
16     int l, r;
17     ll sum, add;
18 }Tree[4 * maxn];
19 
20 void Pushup(int root) {
21     Tree[root].sum = Tree[lson].sum + Tree[rson].sum;
22 }
23 
24 void Pushdown(int l, int r, int root) {
25     int mid = (l + r) >> 1;
26     Tree[lson].add += Tree[root].add;
27     Tree[rson].add += Tree[root].add;
28     Tree[lson].sum += Tree[root].add * (mid - l + 1);
29     Tree[rson].sum += Tree[root].add * (r - mid);
30     Tree[root].add = 0;
31 }
32 
33 void Build(int l, int r, int root) {
34     Tree[root].l = l;
35     Tree[root].r = r;
36     Tree[root].add = 0;
37     if (l == r) {
38         scanf("%lld", &Tree[root].sum);
39         return;
40     }
41     int mid = (l + r) >> 1;
42     Build(l, mid, lson);
43     Build(mid + 1, r, rson);
44     Pushup(root);
45 }
46 
47 void Update(int L, int R, int l, int r, int root, int x) {
48     if (l > R || r < L) return;
49     if (L <= l && r <= R) {
50         Tree[root].add += x;
51         Tree[root].sum += (ll)x * (r - l + 1);
52         return;
53     }
54     if (Tree[root].add) Pushdown(l, r, root);
55     int mid = (l + r) >> 1;
56     Update(L, R, l, mid, lson, x);
57     Update(L, R, mid + 1, r, rson, x);
58     Pushup(root);
59 }
60 
61 ll Query(int L, int R, int l, int r, int root) {
62     if (l > R || r < L) return 0;
63     if (L <= l && r <= R) return Tree[root].sum;
64     if (Tree[root].add) Pushdown(l, r, root);
65     int mid = (l + r) >> 1;
66 
67     ll ans = 0;
68     ans += Query(L, R, l, mid, lson);
69     ans += Query(L, R, mid + 1, r, rson);
70     return ans;
71 }
72 
73 int n, q;
74 
75 int main()
76 {
77     while (scanf("%d%d", &n, &q) != EOF) {
78         Build(1, n, 1);
79         char op[10];
80         for (int i = 1; i <= q; i++) {
81             scanf("%s", op);
82             if (op[0] == 'Q') {
83                 int x, y;
84                 scanf("%d%d", &x, &y);
85                 printf("%lld
", Query(x, y, 1, n, 1));
86             }
87             else {
88                 int x, y, d;
89                 scanf("%d%d%d", &x, &y, &d);
90                 Update(x, y, 1, n, 1, d);
91             }
92         }
93     }
94     return 0;
95 }