Willan_Lian @ 2023-11-17 17:45:57
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int A[100010];
long long C[400010];
long long b[400010];
long long Ans=0;
void insert(int lr,int rr,int idx) {
if(lr==rr) {
C[idx]=A[lr];
return ;
}
int mid=lr+(rr-lr>>1);
insert(lr,mid,idx*2);
insert(mid+1,rr,idx*2+1);
C[idx]=C[idx*2]+C[idx*2+1];
}
long long Sum(int lr,int rr,int ST,int ED,int idx) {
if(lr<=ST && ED<=rr) return C[idx];
int mid=ST+(ED-ST>>1);
long long Ans=0;
if(lr<=mid) Ans+=Sum(lr,rr,ST,mid,idx*2);
if(rr>mid) Ans+=Sum(lr,rr,mid+1,ED,idx*2+1);
return Ans;
}
void update(int lr, int rr, int ST, int ED, int idx,long long d){
if(lr<=ST && ED<=rr){
C[idx]+=(ED-ST+1)*d;
b[idx]+=d;
return;
}
int mid=ST+((ED-ST)>>1);
if(b[idx] && ST!=ED){
C[idx*2]+=b[idx]*(mid-ST+1);
C[idx*2+1]+=b[idx]*(ED-mid);
b[idx*2]+=b[idx],b[idx*2+1]+=b[idx];
b[idx]=0;
}
if(lr<=mid) update(lr,rr,ST,mid,idx*2,d);
if(rr>mid) update(lr,rr,mid+1,ED,idx*2+1,d);
C[idx]=C[idx*2]+C[idx*2+1];
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&A[i]);
insert(1,n,1);
for(int i=1; i<=m; i++){
int x;
scanf("%d",&x);
if(x==1){
int y,z;
long long w;
scanf("%d%d%lld",&y,&z,&w);
update(y,z,1,n,1,w);
}
if(x==2){
int y,z;
scanf("%d%d",&y,&z);
printf("%lld\n",Sum(y,z,1,n,1));
}
}
return 0;
}
by zdc_ @ 2023-11-17 18:19:50
在 Sum 函数里也需要懒标记下传吧