POJ -- 3468

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 53255		Accepted: 15926
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

4
55
9
15

思路：线段树，节点区间的和由sum和add组成，更新：当区间正好匹配时就直接node[k].add += add,return，否则把和加在sum里，递归更新子区间。查找时:如果区间匹配就直接返回node[k].sum + (node[k].right - node[k].left + 1) * node[k].add，否则将和加在sum中，add向子区间传递。

AC代码：

  1 /*************************************************************************
  2     > File Name:        inter.cpp
  3     > Author:         wangzhili
  4     > Mail:           wangstdio.h@gmail.com
  5     > Created Time:   2014/2/27 星期四 14:16:52
  6  ************************************************************************/
  7 
  8 #include<iostream>
  9 #include<cstdio>
 10 using namespace std; 
 11 #define MAX 100005 
 12 class TreeNode
 13 {
 14     public:
 15         int left; 
 16         int right; 
 17         int mid; 
 18         long long int sum; 
 19         long long int add; 
 20 }; 
 21 TreeNode node[4*MAX];
 22 void BuildTree(int k, int l, int r)
 23 {
 24     node[k].left = l; 
 25     node[k].right = r;
 26     node[k].mid = (l + r) >> 1; 
 27     node[k].sum = 0; 
 28     node[k].add = 0; 
 29     if(l == r)
 30         return ; 
 31     int mid = (l + r) >> 1; 
 32     BuildTree(k << 1, l, mid); 
 33     BuildTree(k << 1|1, mid+1, r); 
 34 }
 35 
 36 void UpdateTree(int k, int l, int r, long long int add)
 37 {
 38     if(node[k].left == l && node[k].right == r)
 39     {
 40         node[k].add += add; 
 41         return ; 
 42     }
 43     node[k].sum += (r-l+1) * add; 
 44     if(node[k].mid < l)
 45         UpdateTree(k << 1|1, l, r, add); 
 46     else if(node[k].mid >= r)
 47         UpdateTree(k << 1, l, r, add); 
 48     else
 49     {
 50         UpdateTree(k << 1, l, node[k].mid, add); 
 51         UpdateTree(k << 1|1, node[k].mid + 1, r, add); 
 52     }
 53 }
 54 
 55 long long int GetSum(int k, int l, int r)
 56 {
 57     if(node[k].left == l && node[k].right == r)
 58         return node[k].sum + (node[k].right - node[k].left + 1) * node[k].add; 
 59     node[k << 1].add += node[k].add; 
 60     node[k << 1|1].add += node[k].add; 
 61     node[k].sum += (node[k].right - node[k].left + 1) * node[k].add; 
 62     node[k].add = 0; 
 63     if(node[k].mid < l)
 64         return GetSum(k << 1|1, l, r); 
 65     else if(node[k].mid >= r)
 66         return GetSum(k << 1, l, r); 
 67     else
 68         return GetSum(k << 1, l, node[k].mid) + GetSum(k << 1|1, node[k].mid + 1, r); 
 69 }
 70 
 71 int main(int argc, char const *argv[]) 
 72 {
 73     int n, i, m, l, r, num; 
 74     char str[2]; 
 75     freopen("in.c", "r", stdin); 
 76     while(~scanf("%d%d", &n, &m))
 77     {
 78         BuildTree(1, 1, n); 
 79         for(i = 1; i <= n; i ++)
 80         {
 81             scanf("%d", &num); 
 82             UpdateTree(1, i, i, num); 
 83         }
 84         for(i = 0; i < m; i ++)
 85         {
 86             scanf("%s", str);
 87             if(str[0] == 'Q')
 88             {
 89                 scanf("%d%d", &l, &r); 
 90                 printf("%lld
", GetSum(1, l, r)); 
 91             }
 92             else
 93             {
 94                 scanf("%d%d%d", &l, &r, &num); 
 95                 UpdateTree(1, l, r, num); 
 96             }
 97         }
 98     }
 99     return 0; 
100 }