You have $N$ integers, $A_1, A_2, ... , 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.

Input

The first line contains two numbers $N$ and $Q$. $1 \leq N,Q \leq 100000$. The second line contains $N$ numbers, the initial values of $A_1, A_2, ... , A_N$. $-1000000000 \leq Ai \leq 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 \leq c \leq 10000$. Q a b means querying the sum of $A_a, A_a+1, ... , A_b$.

Output

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

Time limit 5000 ms

Case time limit 2000 ms

Mem limit 131072 kB

---

代码：

#include<cstdio>
#include<algorithm>
#define lson o<<1
#define rson o<<1|1
#define nmid int mid=(nowl+nowr)>>1
using namespace std;
const int maxn=1e5+5;
long long t[maxn<<2],lazy[maxn<<2],a[maxn];
void push_up(int o){
	t[o]=t[lson]+t[rson];
}
void push_down(int nowl,int nowr,int mid,int o){
	if(!lazy[o]) return;
	lazy[lson]+=lazy[o];
	lazy[rson]+=lazy[o];
	t[lson]+=lazy[o]*(mid-nowl+1);
	t[rson]+=lazy[o]*(nowr-mid);
	lazy[o]=0;
}
void build(int nowl,int nowr,int o){
	lazy[o]=0;
	if(nowl==nowr){
		t[o]=a[nowl];
		return;
	}
	nmid;
	build(nowl,mid,lson);
	build(mid+1,nowr,rson);
	push_up(o);
}
long long query(int nowl,int nowr,int l,int r,int o){
	if(l<=nowl&&nowr<=r){
		return t[o];
	}
	nmid;
	push_down(nowl,nowr,mid,o);
	long long result=0;
	if(l<=mid) result+=query(nowl,mid,l,r,lson);
	if(r>mid) result+=query(mid+1,nowr,l,r,rson);
	return result;
}
void update(int nowl,int nowr,int l,int r,int o,long long val){
	if(l<=nowl&&nowr<=r){
		t[o]+=val*(nowr-nowl+1);
		lazy[o]+=val;
		return;
	}
	nmid;
	push_down(nowl,nowr,mid,o);
	if(l<=mid) update(nowl,mid,l,r,lson,val);
	if(r>mid) update(mid+1,nowr,l,r,rson,val);
	push_up(o);
}


int n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(long long i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	for(long long i=1;i<=m;++i){
		char sw='\n';
		while(sw!='C'&&sw!='Q') scanf("%c",&sw);
		if(sw=='C'){
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			update(1,n,x,y,1,k);
		}
		else{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(1,n,x,y,1));
		}
	}
    return 0;
}

线段树写的代码，洛谷P3372（因为很像）过了，但是改一下在vjudge就要么RE要么WA....