View Code of Problem 3073

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
//线段树 
struct Node{
	int l,r;
	ll w,flag;
	Node(){
	};
	Node(int _l,int _r,ll _v,ll _f){
		flag=_f,l=_l,r=_r,w=_v;	
	};
	int mid(){
		return (l+r)/2;
	};
	
};

Node a[maxn*4];
void build(int k,int l,int r){		//建树 
	a[k]=Node(l,r,0,0);
	if(a[k].l==a[k].r){
		scanf("%lld",&a[k].w);
		return;
	}
	build(k<<1,l,(l+r)/2);
	build(k<<1|1,(l+r)/2+1,r);
	a[k].w=a[k<<1].w+a[k<<1|1].w;
}

void down(int k){					//延迟标记下传 
	a[k<<1].flag+=a[k].flag;
	a[k<<1|1].flag+=a[k].flag;
	a[k<<1].w+=a[k].flag*(a[k<<1].r-a[k<<1].l+1);
	a[k<<1|1].w+=a[k].flag*(a[k<<1|1].r-a[k<<1|1].l+1);
	a[k].flag=0;
}

ll res;

void update(int k,int x,int y,ll z){	//区间更新 
	if(a[k].l>=x&&a[k].r<=y){
		a[k].w+=z*(a[k].r-a[k].l+1);
		a[k].flag+=z;
		return;
	}
	if(a[k].flag)
		down(k);
	if(x<=a[k].mid())
		update(k<<1,x,y,z);
	if(y>a[k].mid())
		update(k<<1|1,x,y,z);
	a[k].w=a[k<<1].w+a[k<<1|1].w;
	
}

ll ans;
void query(int k,int x,int y){			//区间查询 
	if(a[k].l>=x&&a[k].r<=y){
		res+=a[k].w;
		return;
	}

	if(a[k].flag)
		down(k);
	if(x<=a[k].mid())
		query(k<<1,x,y);
	if(y>a[k].mid())
		query(k<<1|1,x,y);
	a[k].w=a[k<<1].w+a[k<<1|1].w;	
}


int main()  
{  
    int n,m;
    ll val;
    while(~scanf("%d%d",&n,&m)) {
        build(1,1,n);
        string req;
       	while(m--){
            cin >> req;
            res=0;
			if(req=="Q")
			{
				int x,y;
				scanf("%d %d",&x,&y);
				query(1,x,y);
				printf("%lld\n",res);
			}
			else
			{
				int x,y;
				ll z;
				scanf("%d %d %lld",&x,&y,&val);
				update(1,x,y,val);
			}
        }
    }
    return 0;
}