3468-A Simple Problem with Integers 线段树（区间增减，区间求和）

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 110077		Accepted: 34272
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
题意：n个数字，q次操作，每次可以区间增减，或者查询区间的和

 1 #include<cstdio>
 2 #define lson l,m,rt<<1
 3 #define rson m+1,r,rt<<1|1
 4 #define MAXN 100100
 5 #define LL long long 
 6 LL sum[MAXN<<2];
 7 LL add[MAXN<<2];
 8 int n,q;
 9 char s[2];
10 void putup(int rt)
11 {
12     sum[rt] = sum[rt<<1]+sum[rt<<1|1];
13 }
14 void putdown(int rt,int m)
15 {
16     if (add[rt])
17     {
18         add[rt<<1] += add[rt];
19         add[rt<<1|1] += add[rt];
20         sum[rt<<1] += (m-(m>>1))*add[rt];
21         sum[rt<<1|1] += (m>>1)*add[rt];
22         add[rt] = 0;
23     }
24 }
25 void build(int l,int r,int rt)
26 {
27     add[rt] = 0;
28     if (l==r)
29     {
30         scanf("%lld",&sum[rt]);
31         return ;
32     }
33     int m = (l+r)>>1;
34     build(lson);
35     build(rson);
36     putup(rt);
37 }
38 void update(int l,int r,int rt,int L,int R,int c)
39 {
40     if (L<=l && r<=R)
41     {
42         add[rt] += c;
43         sum[rt] += (LL)c*(r-l+1);
44         return ;
45     }
46     putdown(rt,r-l+1);
47     int m = (l+r)>>1;
48     if (L<=m) update(lson,L,R,c);
49     if (R>m)  update(rson,L,R,c);
50     putup(rt);
51 }
52 LL query(int l,int r,int rt,int L,int R)
53 {
54     if (L<=l && r<=R)
55     {
56         return sum[rt];
57     }
58     putdown(rt,r-l+1);
59     LL ret = 0;
60     int m = (l+r)>>1;
61     if (L<=m) ret += query(lson,L,R);
62     if (R>m)  ret += query(rson,L,R);
63     return ret;
64 }
65 int main()
66 {
67     scanf("%d%d",&n,&q);
68     build(1,n,1);
69     while (q--)
70     {
71         int x,y,z;
72         scanf("%s",s);
73         if (s[0]=='C')
74         {
75             scanf("%d%d%d",&x,&y,&z);
76             update(1,n,1,x,y,z);
77         }
78         else 
79         {
80             scanf("%d%d",&x,&y);
81             printf("%lld
",query(1,n,1,x,y));
82         }
83     }
84     return 0;
85 }