kuangbin专题七：C题 A Simple Problem with Integers

C - A Simple Problem with Integers

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

Hint

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

题意：区间累加，区间查询求和

思路：线段树直接写就好，模板题目（注意做好延迟更新）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ; 

#define maxn 110000 
#define LL long long
LL N , Q ; 
char ch ; 
LL a , b , c ;  
LL num[maxn] ; 

struct node {
    LL l , 
        r ,
        add ,
        sum ; 
};

node tree[maxn*4] ; 

void build(LL root , LL l , LL r ){
    tree[root].l = l ; 
    tree[root].r = r ; 
    tree[root].add = 0 ; 
    if( l == r ){
        tree[root].sum = num[l] ; 
        return;
    }
    
    int mid = (l+r)/2 ; 
    build(root*2 , l , mid ) ; 
    build(root*2+1 , mid+1 , r ) ; 
    
    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum ; 
     
}

void update(LL root , LL s , LL e , LL value){
    if(e < tree[root].l || tree[root].r < s){
        return;
    }
    
    if(s<= tree[root].l && tree[root].r <= e){
        tree[root].sum += (tree[root].r - tree[root].l+1) * value ; 
        tree[root].add += value ; 
        return;
    }
    // 延迟更新 
    LL add = tree[root].add ; 
    if(add){
        tree[root*2].add += add ; 
        tree[root*2].sum += (tree[root*2].r-tree[root*2].l+1) * add ; 
        
        tree[root*2+1].add += add ; 
        tree[root*2+1].sum += (tree[root*2+1].r-tree[root*2+1].l+1) * add ;      
    
        tree[root].add = 0 ; 
    }
    int mid = (tree[root].l + tree[root].r)/2 ; 
    if(e <= mid){
        update(root*2 , s , e , value ) ; 
    } else if(mid<s){
        update(root*2+1 , s , e , value ) ; 
    } else if( s <= mid&&mid < e ) {
        update(root*2 , s , mid , value ) ; 
        update(root*2+1 , mid+1 , e , value ) ; 
    }
    
    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum ; 
    
}

LL query(LL root , LL s , LL e){
    if(e < tree[root].l || tree[root].r < s){
        return 0 ;
    }
    
    if(s<=tree[root].l && tree[root].r <=e){
        return tree[root].sum ; 
        return 0 ;
    }
    // 延迟更新 
    LL add = tree[root].add ; 
    if(add){
        tree[root*2].add += add ; 
        tree[root*2].sum += (tree[root*2].r-tree[root*2].l+1) * add ; 
        
        tree[root*2+1].add += add ; 
        tree[root*2+1].sum += (tree[root*2+1].r-tree[root*2+1].l+1) * add ;      
    
        tree[root].add = 0 ; 
    }
    
    LL mid = (tree[root].l+ tree[root].r)/2 ; 
    if(e<=mid){
        return query(root*2 , s , e ) ; 
    } else if(mid<s){
        return query(root*2+1 , s , e ) ; 
    } else if(s<=mid && mid <e){
        return query(root*2 , s,  mid ) + query(root*2+1 , mid+1 , e ) ; 
    }
    
}


int main(){
    
    while(~scanf("%lld %lld" , &N , &Q)){
        for(int i=1 ; i<=N ; i++){
            scanf("%lld" , &num[i]) ; 
        }
        build(1 , 1 , N ) ; 
        
        for(int i=1 ; i<=Q ; i++){
            scanf(" %c" , &ch) ; 
            if( ch == 'Q'){
                scanf("%lld %lld" , &a , &b) ; 
                printf("%lld
" , query(1 , a , b )) ; 
            } else if(ch == 'C'){
                scanf("%lld %lld %lld" , &a , &b , &c) ; 
                update(1 , a , b , c ) ; 
            }
        }
    }
    return 0 ; 
}

View Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ; 

#define maxn 110000 
#define LL long long
LL N , Q ; 
char ch ; 
LL a , b , c ;  
LL num[maxn] ; 
LL result ; 

struct node {
    LL l , 
        r ,
        add ,
        sum ; 
};

node tree[maxn*4] ; 

void build(LL root , LL l , LL r ){
    tree[root].l = l ; 
    tree[root].r = r ; 
    tree[root].add = 0 ; 
    if( l == r ){
        tree[root].sum = num[l] ; 
        return;
    }
    
    int mid = (l+r)/2 ; 
    build(root*2 , l , mid ) ; 
    build(root*2+1 , mid+1 , r ) ; 
    
    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum ; 
     
}

void update(LL root , LL s , LL e , LL value){
    if(e < tree[root].l || tree[root].r < s){
        return;
    }
    
    if(s<= tree[root].l && tree[root].r <= e){
        tree[root].sum += (tree[root].r - tree[root].l+1) * value ; 
        tree[root].add += value ; 
        return;
    }
    
    LL add = tree[root].add ; 
    if(add){
        tree[root*2].add += add ; 
        tree[root*2].sum += (tree[root*2].r-tree[root*2].l+1) * add ; 
        
        tree[root*2+1].add += add ; 
        tree[root*2+1].sum += (tree[root*2+1].r-tree[root*2+1].l+1) * add ;      
    
        tree[root].add = 0 ; 
    }

        update(root*2 , s , e , value ) ; 

        update(root*2+1 , s , e , value ) ; 

    tree[root].sum = tree[root*2].sum + tree[root*2+1].sum ; 
    
}

void query(LL root , LL s , LL e){
    if(e < tree[root].l || tree[root].r < s){
        return;
    }
    
    if(s<=tree[root].l && tree[root].r <=e){
        result += tree[root].sum ; 

        return;

    }
    LL add = tree[root].add ; 
    if(add){
        tree[root*2].add += add ; 
        tree[root*2].sum += (tree[root*2].r-tree[root*2].l+1) * add ; 
        
        tree[root*2+1].add += add ; 
        tree[root*2+1].sum += (tree[root*2+1].r-tree[root*2+1].l+1) * add ;      
    
        tree[root].add = 0 ; 
    }
    query(root*2 , s , e ) ;
    query(root*2+1 , s , e ) ; 

}


int main(){
    
    while(~scanf("%lld %lld" , &N , &Q)){
        for(int i=1 ; i<=N ; i++){
            scanf("%lld" , &num[i]) ; 
        }
        build(1 , 1 , N ) ; 
        
        for(int i=1 ; i<=Q ; i++){
            scanf(" %c" , &ch) ; 
            if( ch == 'Q'){
                result = 0 ; 
                scanf("%lld %lld" , &a , &b) ; 
                query(1 , a,  b ) ; 
                printf("%lld
" , result ) ; 
            } else if(ch == 'C'){
                scanf("%lld %lld %lld" , &a , &b , &c) ; 
                update(1 , a , b , c ) ; 
            }
        }
    }
    return 0 ; 
}

View Code