POJ-3468

题目描述

You have N integers, A1, A2, ... , AN. 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Sample Input

1
2
3
4
5
6
7
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

Output

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

Sample Output

1
2
3
4
4
55
9
15

Hint

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// #include<bits/stdc++.h>
#include<stdio.h>
// using namespace std;
const int Max = 1e5+2;
#define ll long long
#define lson rt<<1, l, mid
#define rson (rt<<1)+1, mid+1, r

struct Node
{
    int l,r;
    ll sum,add;
    /* data */
}tree[Max<<2];

void push_up(int rt){   // 从下往上更新sum
    tree[rt].sum = tree[rt<<1].sum+tree[(rt<<1)+1].sum;
}
void push_down(int rt){ // 向下更新add和sum
    if(tree[rt].add!=0){
        tree[rt<<1].add += tree[rt].add;
        tree[(rt<<1)+1].add += tree[rt].add;
        tree[rt<<1].sum += (tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].add;
        tree[(rt<<1)+1].sum += (tree[(rt<<1)+1].r-tree[(rt<<1)+1].l+1)*tree[rt].add;
        tree[rt].add = 0;
    }
}

void build(int rt, int l, int r){   // 建线段树
    tree[rt].l = l; tree[rt].r = r;

    if(l == r){
        scanf("%lld", &tree[rt].sum);
        return;
    }

    int mid = (l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int a, int b, ll c){   // 【a, b】区间每个数+c，使用lazy
    if(tree[rt].l>=a && tree[rt].r<=b){ // 如果更新的区间 包含了 当前节点的区间
        tree[rt].sum += (tree[rt].r-tree[rt].l+1)*c;
        tree[rt].add += c;
        return;
    }

    push_down(rt);
    int mid = (tree[rt].l+tree[rt].r) >> 1;
    if(a <= mid) update(rt<<1, a, b, c);
    if(b > mid) update((rt<<1)+1, a, b, c);
    push_up(rt);    
}

ll quary(int rt, int a, int b){   // 查询【Na, Nb】区间和
    if(tree[rt].l>=a && tree[rt].r<=b){ // 如果更新的区间 包含了 当前节点的区间
        return tree[rt].sum;
    }

    push_down(rt);
    ll ans = 0;
    int mid = (tree[rt].l+tree[rt].r) >> 1;
    if(a <= mid) ans += quary(rt<<1, a, b);
    if(b > mid) ans += quary((rt<<1)+1, a, b);
    return ans;
}


int main(){
    int n, q, a, b;
    ll c;
    char qu;

    // cin >> n >> q;
    scanf("%d%d", &n,&q);
    build(1, 1, n);

    while(q--){
        scanf(" %c", &qu);
        
        if(qu == 'Q'){
            scanf("%d %d", &a, &b);
            printf("%lld\n", quary(1, a, b));
        }else{
            scanf("%d%d%lld", &a,&b, &c);
            update(1, a, b, c);
        } 
        
    }

    // system("pause");
    return 0;
}


/*
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


10 2
1 2 3 4 5 6 7 8 9 10
C 3 6 3
Q 2 4
*/

3468 -- A Simple Problem with Integers (poj.org)