Eva

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3015  Solved: 1281
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. 

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. 

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

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

4
55
9
15

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

/**************************************************************

    Problem: 3212

    User: ictsing

    Language: C++

    Result: Accepted

    Time:44 ms

    Memory:7544 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int mt=100000+5;

long long sum[mt<<2],lazy[mt<<2];

void pushup(int rt)

{

    sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

void build(int l,int r,int rt)

{

    lazy[rt]=0;//%%%%%%%%%%%%%

    if(l==r)

    {

        scanf("%lld",&sum[rt]);

        return ;

    }

    int m=(l+r)>>1;

    build(lson);

    build(rson);

    pushup(rt);

}

void pushdown(int rt,int m)

{

    if(lazy[rt])

    {

        lazy[rt<<1]+=lazy[rt];

        lazy[rt<<1|1]+=lazy[rt];

        sum[rt<<1]+=(m-(m>>1))*lazy[rt];

        sum[rt<<1|1]+=(m>>1)*lazy[rt];

        lazy[rt]=0;

    }

}

void update(int ll,int rr,int add,int l,int r,int rt)

{

    if(ll<=l&&rr>=r)

    {

        sum[rt]+=(long long)((r-l+1)*add);//**********************

        lazy[rt]+=add;

        return ;

    }

    pushdown(rt,r-l+1);

    int m=(l+r)>>1;

    if(ll<=m) update(ll,rr,add,lson);

    if(rr>m) update(ll,rr,add,rson);

    pushup(rt);

}

long long query(int ll,int rr,int l,int r,int rt)

{

    if(ll<=l&&rr>=r)

    {

        return sum[rt];

    }

    pushdown(rt,r-l+1);//!!!!!!!!!!!!!!!!!!

    int m=(l+r)>>1;

    long long  ans=0;

    if(ll<=m) ans+=query(ll,rr,lson);//*************************

    if(rr>m) ans+=query(ll,rr,rson);//**************************************************

    return ans;

}

int main()

{

    int n,q;

    scanf("%d%d",&n,&q);

    build(1,n,1);

    //cout<<q<<"=============="<<endl;

    for(int i=1;i<=q;i++)

    {

        char op[2];

        scanf("%s",op);

        int a,b,c;

        scanf("%d%d",&a,&b);

        if(op[0]=='Q')

        {

            printf("%lld\n",query(a,b,1,n,1));

        }

        else

        {

            scanf("%d",&c);

            update(a,b,c,1,n,1);

        }

    }

    return 0;

}