poj3468

发表于 | 分类于 ， ， | 阅读数 次

链接:poj3468

Description

  • 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.

    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

    题解

  • 区间修改区间查询
  • 维护个懒标记就好，具体看代码
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
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long 
using namespace std;
const int N=1e7;
ll tr[N<<2],a[N],add[N];
int n,m;

void build(int o,int l,int r){
    if(l==r)tr[o]=a[l];
    else {
        int mid=l+r>>1;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        tr[o]=tr[o<<1]+tr[o<<1|1];
    }
}

void pushdown(int o,int l,int r){
    if(add[o]){
        add[o<<1]+=add[o];             //懒标记下放
        add[o<<1|1]+=add[o];       
        int mid=l+r>>1;
        tr[o<<1]+=add[o]*(mid-l+1);
        tr[o<<1|1]+=add[o]*(r-mid);
        add[o]=0;                   
    }
}

void update(int o,int l,int r,int L,int R,ll k){
    if(L<=l&&R>=r){
        add[o]+=k;
        tr[o]+=k*(r-l+1);
        return ;            //做个标记，不下放
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    if(L<=mid)update(o<<1,l,mid,L,R,k);
    if(R>mid)update(o<<1|1,mid+1,r,L,R,k);
    tr[o]=tr[o<<1]+tr[o<<1|1];
}

ll ask(int o,int l,int r,int L,int R){
    if(L<=l&&R>=r)return tr[o];
    pushdown(o,l,r);
    int mid=l+r>>1;
    ll ans=0;
    if(L<=mid)ans+=ask(o<<1,l,mid,L,R);
    if(R>=mid+1)ans+=ask(o<<1|1,mid+1,r,L,R);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        rep(i,1,n)cin>>a[i];
        build(1,1,n);
        while(m--){
            char p;
            ll x,y;
            cin>>p>>x>>y;
            if(p=='C'){
                ll k;
                cin>>k;
                update(1,1,n,x,y,k);
            }
            else cout<<ask(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}