# C - A Simple Problem with Integers

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.

Input
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.

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
4
55
9
15

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

using namespace std;
const int maxn=1e5+100;
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1
typedef long long ll;
ll sum[maxn << 2];
ll lazy[maxn << 2];

void pushup(ll root)
{
sum[root] = sum[root << 1] + sum[root << 1 | 1];
}

void pushdown(ll root, ll ln, ll rn)
{
if(lazy[root])
{
lazy[root << 1] += lazy[root];
lazy[root << 1 | 1] += lazy[root];

sum[root << 1] += lazy[root] * ln;
sum[root << 1 | 1] += lazy[root] * rn;

lazy[root] = 0;
}
}

void build(ll left, ll right, ll root)
{
if(left == right)
{
scanf("%lld",&sum[root]);
return;
}
ll mid = left + right >> 1;
build(lson);
build(rson);
pushup(root);
}

ll query(ll left, ll right, ll root, ll L, ll R)
{
if(L <= left && right <= R)
{
return sum[root];
}

ll mid = left + right >> 1;
pushdown(root , mid - left + 1, right - mid);

ll ans = 0;
if(L <= mid)
ans += query(lson, L, R);
if(R > mid)
ans += query(rson, L, R);
return ans;
}

void update(ll left, ll right, ll root, ll L, ll R, ll c)
{
if(L <= left && right <= R)
{
sum[root] += c * (right - left + 1);
lazy[root] += c;
return;
}

ll mid = left + right >> 1;
pushdown(root, mid - left + 1, right - mid);

if(L <= mid)
update(lson, L, R, c);
if(R > mid)
update(rson, L, R, c);

pushup(root);
}

int main()
{
ll n, q;
char op[2];
scanf("%lld%lld",&n,&q);
build(1, n, 1);
while(q--)
{
ll l, r;
ll c;
scanf("%s",op);
if(op[0] == 'Q')
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(1, n, 1, l, r));
}
else
{
scanf("%lld%lld%lld",&l,&r,&c);
update(1, n, 1, l, r, c);
}
}
return 0;
}