kuangbin——线段树专题 C - A Simple Problem with Integers

C - A Simple Problem with Integers

Time Limit:5000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu

Submit  Status

Description

给出了一个序列，你需要处理如下两种询问。

"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。

"Q a b" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.

第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。

接下来Q行询问，格式如题目描述。

Output

对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。

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

/*************************************************************************
	> File Name: C.cpp
	> Author:chudongfang 
	> Mail:1149669942@qq.com 
	> Created Time: 2016年08月04日 星期四 08时17分23秒
 ************************************************************************/

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;

#define M 100005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1


ll sum[M<<2];
ll add[M<<2];


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

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

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

    int m = (l+r)>>1;
    build(lson);
    build(rson);
    pushplus(rt);
    
}


void update(int L,int R,int c,int l,int r ,int rt)
{
    if(L <= l && r<=R)
    {
        add[rt] += c;
        sum[rt] +=(ll)c * (r-l+1);
        return ;
    }
    
    pushdown(rt , r - l + 1); 
    
    int m = (l+r)>>1;
    
    if(L<=m)
        update(L,R,c,lson);
    if(R>m)    
        update(L,R,c,rson);
    pushplus(rt);

}


ll query(int L,int R,int l,int r ,int rt)
{
    if(L<=l && r<=R)
    {
        return sum[rt];
    }
    
    pushdown(rt , r - l + 1);    
    int m = (l + r) >>1;
    ll ans = 0;
    if(L<=m)
        ans += query(L,R,lson);
    if(R>m)
        ans += query(L,R,rson);
    
    return ans;
}




int main(int argc,char *argv[])
{
    int q,a,b,c,n;
    while(scanf("%d %d",&n,&q) == 2)
    {
        build(1,n,1);
        char op[10];
        for(int i=1;i<=q;i++)
        {
            scanf("%s",op);
            if(strcmp(op,"Q") == 0)
            {
                scanf("%d %d",&a,&b);
                printf("%lld\n",query(a,b,1,n,1));
            }
            else if(strcmp(op,"C") == 0)
            {
                scanf("%d %d %d",&a,&b,&c);
                update(a,b,c,1,n,1);
            }

        }
    }
    return 0;
}