A Simple Problem with Integers

链接：

http://poj.org/problem?id=3468

维护区间和

部分数据

input 1
20 10
21 33 39 30 -26 -37 32 18 -32 36 -28 -34 31 8 18 25 36 6 -34 2
C 5 13 -19
Q 19 20 
C 11 12 17
Q 11 20 
C 14 18 -15
C 7 9 -10
Q 18 20 
Q 19 20 
Q 6 15 
C 7 10 -8

output 1
-32
7
-41
-32
-166

input 2
40 20
-79 -37 39 10 57 -48 77 -46 72 -17 11 60 41 -55 -6 -53 56 -18 53 -15 -18 -46 -20 -73 -32 79 47 -21 29 49 76 -46 -16 -25 -27 37 59 15 -64 -51
Q 33 39 
C 29 38 -27
C 5 40 -33
C 15 39 33
Q 30 39 
Q 14 25 
C 26 38 -17
Q 6 15 
Q 8 36 
C 17 39 -7
C 37 39 -4
C 6 33 10
Q 31 37 
C 14 26 -39
C 34 36 -11
Q 37 39 
C 38 40 -23
C 7 14 -9
C 20 35 33
C 19 25 -1

output 2
-21
-185
-260
-208
-558
-273
-111

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <time.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 1e5+10;
struct node {
    ll sum , add;
}st[N*4];
ll x[N];

void pushup(int rt){
    st[rt].sum = st[rt<<1].sum + st[rt<<1|1].sum;
}

void pushdown(int rt, int l, int r){
    if(st[rt].add){
        int m = (l+r)>>1;
        st[rt<<1].sum += st[rt].add*(m-l+1);
        st[rt<<1|1].sum += st[rt].add*(r-m);
        st[rt<<1].add += st[rt].add;
        st[rt<<1|1].add += st[rt].add;
        st[rt].add = 0;
    }
}

void update(int rt, int l, int r, int L, int R, int xx){
    if(L <= l && r <= R) st[rt].add += xx, st[rt].sum += xx*(r - l +1);
    else {
        int m = (l+r) >> 1;
        pushdown(rt, l, r);
        if(L <= m ) update(rt<<1, l, m, L, R, xx);
        if(R > m) update(rt<<1|1, m+1, r, L ,R, xx);
        pushup(rt);
    } 
}

ll query(int rt, int l, int r, int L, int R){//大写为询问
    if(L <= l && r <= R)  return st[rt].sum;
    
    else {
        pushdown(rt, l, r);
        int m = (l+r)>>1;
        ll a = 0;
        if(L <= m) a += query(rt<<1, l, m, L, R); 
        if(R > m) a += query(rt<<1|1, m+1, r, L ,R);
        pushup(rt);
        return a;
    }
}

void build(int rt, int l, int r){
    st[rt].add = 0;
    if(l == r) st[rt].sum = x[l]; 
    else {
        int m = (l+r)>>1;
        build(rt<<1, l, m);
        build(rt<<1|1, m+1, r);
        pushup(rt);
    }
}

int main(){

    int n, q;
    scanf("%d%d",&n, &q);
    for(int i = 1; i <= n ;i++) scanf("%lld",&x[i]); 

    build(1,1,n);

    while(q--){   
        char a[10];
        int l, r, xx;
        scanf("%s",a);
        
        if(a[0] == 'Q'){
            scanf("%d%d",&l, &r);
            cout<< query(1, 1, n, l, r)<<endl;
        }
        else {
            scanf("%d%d%d",&l, &r, &xx);
            update(1, 1, n, l, r, xx);            
        }
    }

    return 0;
}