A Simple Problem with Integers
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 88419 Accepted: 27480
Case Time Limit: 2000MS
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.

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
Hint

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

POJ Monthly--2007.11.25, Yang Yi
题意太简单明了了：定区间，定初始值！然后C区间增加，Q区间查询。
花了两三天，终于学会线段树了，AC之..
4985MS，这时间真心险。。

/*
Source Code

Problem: 3468		User: aclolicon
Memory: 8908K		Time: 4985MS
Language: G++		Result: Accepted
Source Code*/
#include
#include
#define MAXLEN 550050
using namespace std;
typedef long long LL;
struct Node{
	LL l, r, v, lazy;
}node[MAXLEN];
LL n, m, len, cmd;
void update(int i){
	node[i].v += (node[i].r - node[i].l + 1) * node[i].lazy;
	if (node[i].l < node[i].r){
		node[i << 1].lazy += node[i].lazy;
		node[(i << 1) + 1].lazy += node[i].lazy;		
	}
	node[i].lazy = 0;
}
void add(LL i, LL l, LL r, LL v){
	if (node[i].l > r || node[i].r < l) return;
	if (node[i].l >= l && node[i].r <= r){
		node[i].lazy += v;
		return; 
	}
//	cout << i << endl;
	update(i);
	add(i << 1, l, r, v);
	add((i << 1) + 1, l, r, v);
	update(i << 1), 
	update((i << 1) | 1); 
	node[i].v = node[i << 1].v + node[(i << 1) + 1].v;

}
LL query(LL i, LL l, LL r){
	if (node[i].l > r || node[i].r < l) return 0;
	update(i); 
	if (node[i].l >= l && node[i].r <= r) return node[i].v;
	return query(i << 1, l, r) + query((i << 1) + 1, l, r);
}
void build(LL i, LL l, LL r){
	node[i].l = l;
	node[i].r = r;
	node[i].v = 0;
	node[i].lazy = 0;
	if (l == r) return;
	LL mid = (l + r) >> 1;
	build (i << 1, l, mid);
	build ((i << 1) + 1, mid + 1, r);
	return;
}
int main(){
	scanf("%lld%lld", &len, &cmd);
	build(1, 1, len);
	for (int i = 1; i <= len; i++){
		LL t;
		scanf("%lld", &t);
		add(1, i, i, t);
	}
	for (int i = 0; i < cmd; i++){
		char c[10];
		scanf("%s", c);
		if (c[0] == 'Q'){
			LL l, r;
			scanf("%lld%lld", &l, &r);
			printf("%lldn", query(1, l, r)); 
		}
		if (c[0] == 'C'){
			LL l, r, v;
			scanf("%lld%lld%lld", &l, &r, &v);
			add(1, l, r, v);
		}
	}
	return 0;
}

现在来不及了，要回宿舍！明天写一个教程~晚安