A Simple Problem with Integers

Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 162835 Accepted: 50246 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.
不知道为什么用c++写的代码一直tel，改用c语言直接秒过了，毒啊；
ac代码：

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long int ll;
const int N = 100005;
struct node
{
	ll l,r;
	ll s; 
	ll add;
}tree[N<<2];

void build(ll l,ll r,ll i){
	tree[i].l=l;
	tree[i].r=r;
	tree[i].add=0; 
	if(l==r){
		scanf("%lld",&tree[i].s);
		return ;
	}
	ll mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	tree[i].s=tree[i*2].s+tree[i*2+1].s;
}

void pushdown(int i,int m){//m代表区间长度 
	if(tree[i].add){
		tree[i*2].add+=tree[i].add;
		tree[i*2+1].add+=tree[i].add;
		tree[i*2].s+=tree[i].add*(m-(m/2));
		tree[i*2+1].s+=tree[i].add*(m/2);
		tree[i].add=0;
	}
}
ll query(ll l,ll r,int i){
	if(tree[i].l==l&&tree[i].r==r){
		return tree[i].s;
	}else{
		pushdown(i,tree[i].r - tree[i].l + 1);
		ll mid=(tree[i].l+tree[i].r)/2;
		ll ans=0; 
		if(r<=mid){
			ans+= query(l,r,2*i);
		}else if(l>mid){
			ans+= query(l,r,2*i+1);
		}else{
			ans+=query(l,mid,2*i);
			ans+=query(mid+1,r,2*i+1);
		} 
		return ans; 
	}
}
void updata(ll c,ll l,ll r,ll i){
	if(tree[i].l==l&&tree[i].r==r){
		tree[i].add+=c;
		tree[i].s+=(ll)(r-l+1)*c;
		return ;
	}
	if(tree[i].l==tree[i].r)return;
	pushdown(i,tree[i].r-tree[i].l+1);
	ll mid=(tree[i].l+tree[i].r)/2;
	if(r<=mid){
		updata(c,l,r,2*i);
	}else if(l>mid){
	    updata(c,l,r,2*i+1);
	}else{
		updata(c,l,mid,2*i);
		updata(c,mid+1,r,2*i+1);
	} 
	tree[i].s=tree[i*2].s+tree[i*2+1].s;
}
int main()
{
	ll n,q;
	char ch;
	scanf("%lld%lld",&n,&q);
			build(1,n,1);
		for(register int i=1;i<=q;i++){
			ll x,y,z;
			getchar();
			scanf("%c",&ch);
			if(ch=='Q'){
				scanf("%lld%lld",&x,&y);
				printf("%lld\n",query(x,y,1));
			}else{
				scanf("%lld%lld%lld",&x,&y,&z);
					updata(z,x,y,1);
				}
		}
		
}