Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 115624		Accepted: 35897
Case Time Limit: 2000MS

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.

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+1, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

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.

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 100009

#define L 31

#define INF 1000000009

#define eps 0.00000001

/*

线段树 区间更新区间查询

*/

LL a[MAXN],pre[MAXN];

struct node

{

    LL l, r;

    LL data, sum, laz;

}T[MAXN*];

void build(LL p, LL l, LL r)

{

    T[p].data = T[p].sum = T[p].laz = ;

    T[p].l = l, T[p].r = r;

    if (l == r) return;

    LL mid = (l + r) / ;

    build(p * , l, mid);

    build(p *  + , mid + , r);

}

void update(LL p, LL l, LL r, LL v)

{

    //cout << p << ' ' << l << ' ' << r << ' ' << v << endl;

    if (T[p].l >= l && T[p].r <= r)

    {

        T[p].data += v;

        T[p].laz = ;

        T[p].sum += (T[p].r - T[p].l + ) * v;

        return;

    }

    LL mid = (T[p].l + T[p].r) / ;

    if (T[p].laz)

    {

        T[p].laz = ;

        update(p * , T[p].l, mid, T[p].data);

        update(p *  + , mid + , T[p].r, T[p].data);

        T[p].data = ;

    }

    if (r <= mid)

        update(p * , l, r, v);

    else if (l > mid)

        update(p *  + , l, r, v);

    else

    {

        update(p * , l, mid, v);

        update(p *  + , mid + , r, v);

    }

    T[p].sum = T[p * ].sum + T[p *  + ].sum;

}

LL query(LL p, LL l, LL r)

{

    if (l == T[p].l&&r == T[p].r)

        return T[p].sum;

    LL mid = (T[p].l + T[p].r) / ;

    if (T[p].laz)

    {

        T[p].laz = ;

        update(p * , T[p].l, mid, T[p].data);

        update(p *  + , mid + , T[p].r, T[p].data);

        T[p].data = ;

    }

    if (r <= mid)

        return query(p * , l, r);

    else if (l > mid)

        return query(p *  + , l, r);

    else

        return query(p * , l, mid) + query(p *  + , mid + , r);

}

LL n, q;

int main()

{

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

    for (LL i = ; i <= n; i++)

        scanf("%lld", &a[i]), pre[i] = pre[i - ] + a[i];

    char c[];

    LL a, b, d;

    build(,,n);

    while (q--)

    {

        scanf("%s", c);

        if (c[] == 'Q')

            scanf("%lld%lld", &a, &b), printf("%lld\n", query(, a, b) + pre[b] - pre[a-]);

        else

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

    }

}