POJ 3468 A Simple Problem with Integers

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 92522		Accepted: 28778
Case Time Limit: 2000MS

Description

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.

Source

POJ Monthly--2007.11.25, Yang Yi

解析：线段树，区间更新，区间查询。

 1 #include <cstdio>
 2 
 3 struct Node{
 4     int l, r;
 5     long long val, add;
 6 };
 7 Node node[100005<<2];
 8 
 9 void build(int v, int l, int r)
10 {
11     node[v].l = l;
12     node[v].r = r;
13     node[v].add = 0;
14     if(node[v].l == node[v].r){
15         scanf("%I64d", &node[v].val);
16         return;
17     }
18     int mid = (l+r)>>1;
19     build(v<<1, l, mid);
20     build(v<<1|1, mid+1, r);
21     node[v].val = node[v<<1].val+node[v<<1|1].val;
22 }
23 
24 void pushDown(int v)
25 {
26     if(node[v].add){
27         node[v<<1].add += node[v].add;
28         node[v<<1|1].add += node[v].add;
29         int m = node[v].r-node[v].l+1;
30         node[v<<1].val += (m-(m>>1))*node[v].add;
31         node[v<<1|1].val += (m>>1)*node[v].add;
32         node[v].add = 0;
33     }
34 }
35 
36 long long query(int v, int l, int r)
37 {
38     if(node[v].l == l && node[v].r == r)
39         return node[v].val;
40     pushDown(v);    //更新子区间
41     int mid = (node[v].l+node[v].r)>>1;
42     if(r <= mid)
43         return query(v<<1, l, r);
44     else if(l > mid)
45         return query(v<<1|1, l, r);
46     else
47         return query(v<<1, l, mid)+query(v<<1|1, mid+1, r);
48 }
49 
50 void update(int v, int l, int r, int c)
51 {
52     if(node[v].l == l && node[v].r == r){
53         node[v].val += (r-l+1)*c;
54         node[v].add += c;
55         return;
56     }
57     pushDown(v);    //更新子区间
58     int mid = (node[v].l+node[v].r)>>1;
59     if(r <= mid)
60         update(v<<1, l, r, c);
61     else if(l > mid)
62         update(v<<1|1, l, r, c);
63     else{
64         update(v<<1, l, mid, c);
65         update(v<<1|1, mid+1, r, c);
66     }
67     node[v].val = node[v<<1].val+node[v<<1|1].val;
68 }
69 
70 int main()
71 {
72     int N, Q;
73     scanf("%d%d", &N, &Q);
74     build(1, 1, N);
75     char order[5];
76     int a, b, c;
77     while(Q--){
78         scanf("%s", order);
79         if(order[0] == 'Q'){
80             scanf("%d%d", &a, &b);
81             printf("%I64d
", query(1, a, b));
82         }
83         else{
84             scanf("%d%d%d", &a, &b, &c);
85             update(1, a, b, c);
86         }
87     }
88     return 0;
89 }