样例也没过,最后一个输出是19,其他都和样例输出一样
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAX_N = 100005;
long long a[MAX_N];
long long n,m;
struct Node{
long long l,r;
long long pre,add;
}ans[100005];
inline long long lc(long long p){return p*2;}
inline long long rc(long long p){return (p*2)+1;}
void debug(){
for(int i=1;i<=1<<n;i++){
cout<<"pre:"<<ans[i].pre<<' '<<"add:"<<ans[i].add<<endl;
}
}
void push_up(long long p){
ans[p].pre=ans[lc(p)].pre+ans[rc(p)].pre;
}
void push_down(long long l,long long r,long long p){
long long mid = (l+r)>>1;
ans[lc(p)].add+=ans[p].add;
ans[lc(p)].pre+=(mid-l+1)*ans[p].add;
ans[rc(p)].pre+=(r-mid+1)*ans[p].add;
ans[p].add=0;
}
void update(long long nl,long long nr,long long l,long long r,long long p,long long d){
if(l>=nl&&r<=nr){
ans[p].pre+=(r-l+1)*d;
ans[p].add+=d;
return;
}
push_down(l,r,p);
long long mid = (l+r)>>1;
if(nl<=mid)update(nl,nr,l,mid,lc(p),d);
if(nr>mid)update(nl,nr,mid+1,r,rc(p),d);
push_up(p);
}
long long query(long long nl,long long nr,long long l,long long r,long long p){
if(l>=nl&&r<=nr)return ans[p].pre;
push_down(l,r,p);
long long res=0;
long long mid=(l+r)>>1;
if(nl<=mid)res+=query(nl,nr,l,mid,lc(p));
if(nr>mid)res+=query(nl,nr,mid+1,r,rc(p));
return res;
}
void build(long long l,long long r,long long p){
if(l==r){ans[p].pre=a[l];return;}
long long mid=(l+r)>>1;
build(l,mid,lc(p));
build(mid+1,r,rc(p));
push_up(p);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=m;i++){
int T;
cin>>T;
switch(T){
case 1:{
long long l,r,d;
cin>>l>>r>>d;
update(l,r,1,n,1,d);
break;
}
case 2:{
long long l,r;
cin>>l>>r;
cout<<query(l,r,1,n,1)<<endl;
break;
}
}
}
return 0;
}