正在思考人缘关系的WNJXYK忽然被数学老师点起来回答问题了，数学老师知道他走神了于是想出个难一点的问题惩罚他。数学老师一转身，黑板上就出现了一个长度为N的序列 A1, A2, … , AN ，数学老师以谢尔曼M1坦克每分钟350发
穿甲、爆破燃烧，瞬间完成的速度要求WNJXYK完成他如下的若干操作：
1.给这个序列一段区间每个位置增减同一个数字
2.询问一个区间的和令人惊讶的是WNJXYK总能立刻给出回答，但是老师却无法验证他是不是在口胡，于是他想让你写个程序帮助他。Input
第一行包含两个数字N，Q（1 ≤ N,Q ≤ 100000）
第二行包含N个数字，表示数列的初始状态。（ -1000000000 ≤ Ai ≤ 1000000000）
接下来Q行，每行一个操作：
"C a b c" 表示给 Aa, Aa+1, … , Ab. 每个位置的数字增加c （-10000 ≤ c ≤ 10000）
"Q a b" 表示询问 Aa, Aa+1, … , Ab. 的区间和Output
输出若干行，开始你的表演。Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 5 5
Q 1 10
Q 1 5
C 1 5 3
Q 1 5Sample Output
5
55
15
30Hint
区间和有可能超过32位整型本题使用区间模拟即可,下面是模板 根据题意相应修改判断即可
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAX_N=100000;
const ll INF = 0x3f3f3f3f;ll tree[800000];
ll lazy[802020];
//初始化
void init(ll n){for(ll i=0;i<n*4;i++){tree[i]=0;}
}
//建树
void build(ll l,ll r,ll root){if(l==r){cin>>tree[root];return;}ll mid=(l+r)>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);tree[root]=tree[root<<1]+tree[root<<1|1];
}
//lazy更新处理
void PushDown(ll root,ll m){if(lazy[root]){lazy[root<<1]+=lazy[root];//注意这里是+= 修改换成=即可lazy[root<<1|1]+=lazy[root];//注意这里是+= 修改换成=即可tree[root<<1]+=(m-(m>>1))*lazy[root];//注意这里是+= 修改换成=即可tree[root<<1|1]+=(m>>1)*lazy[root];//注意这里是+= 修改换成=即可lazy[root]=0;}
}
//区间更改
void changearea(ll l,ll r,ll root,ll L,ll R,ll val){if(L<=l&&R>=r){lazy[root]+=val;//注意这里是+= 修改换成=即可tree[root]+=(ll)val*(r-l+1);//注意这里是+= 修改换成=即可return;}PushDown(root,r-l+1);ll mid=(l+r)>>1;if(L<=mid)changearea(l,mid,root<<1,L,R,val);if(R>mid)changearea(mid+1,r,root<<1|1,L,R,val);tree[root]=tree[root<<1]+tree[root<<1|1];
}//单点修改
void changepoint(ll l,ll r,ll root,ll poll,ll val){if(l==r){tree[root]+=val;return;}ll mid=(l+r)>>1;if(poll<=mid)changepoint(l,mid,root<<1,poll,val);else changepoint(mid+1,r,root<<1|1,poll,val);tree[root]=tree[root*2]+tree[root*2+1];
}//区间查询(带lazy标记)
ll searcharea(ll l,ll r,ll root,ll L,ll R){if(L<=l&&R>=r)return tree[root];PushDown(root,r-l+1);ll mid=(l+r)>>1;if(R<=mid)return searcharea(l,mid,root<<1,L,R);if(L>mid)return searcharea(mid+1,r,root<<1|1,L,R);elsereturn searcharea(l,mid,root<<1,L,mid)+searcharea(mid+1,r,root<<1|1,mid+1,R);
}
//区间查询(单点)
ll searchpoint(ll l,ll r,ll root,ll L,ll R){if(L<=l&&R>=r)return tree[root];ll mid=(l+r)>>1;if(R<=mid)return searchpoint(l,mid,root<<1,L,R);else if(L>mid)return searchpoint(mid+1,r,root<<1|1,L,R);elsereturn searchpoint(l,mid,root<<1,L,mid)+searchpoint(mid+1,r,root<<1|1,mid+1,R);
}
int main(){ios::sync_with_stdio(false);ll n,q;cin>>n>>q;init(n);build(1,n,1);string s;ll a,b,c;for(ll i=0;i<q;i++){cin>>s;if(s=="Q"){cin>>a>>b;cout<<searcharea(1,n,1,a,b)<<endl;}else{cin>>a>>b>>c;changearea(1,n,1,a,b,c);}}return 0;
}