wanghx1 @ 2024-07-09 10:08:15
#include<bits/stdc++.h>
using namespace std;
#define N 1000500
#define ed puts("")
#define pn puts("No")
#define int long long
#define py puts("Yes")
#define mod 1000000007
#define p_ putchar(' ')
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int ksm(int a,int b,int p){
int ans=1%p;
while(b>0){
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans%p;
}
int mod1(int x,int p){
return (x%p+p)%p;
}
int n,m,a[N],sum[N<<2],add[N<<2],id,x,y,k;
void pushup(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
if(l==r){
sum[rt]=a[l];
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void pushdown(int rt,int ln,int rn){
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=add[rt]*ln;
sum[rt<<1|1]+=add[rt]*rn;
add[rt]=0;
}
}
void update(int rt,int l,int r,int L,int R,int c){
if(L<=l&&r<=R){
sum[rt]+=c*(r-l+1);
add[rt]+=c;
return ;
}
int mid=l+r>>1;
pushdown(rt,mid-l+1,r-m);
if(L<=mid) update(rt<<1,l,mid,L,R,c);
if(R>mid) update(rt<<1|1,mid+1,r,L,R,c);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R) return sum[rt];
int mid=l+r>>1;
pushdown(rt,mid-l+1,r-mid);
int ans=0;
if(L<=mid) ans+=query(rt<<1,l,mid,L,R);
if(R>mid) ans+=query(rt<<1|1,mid+1,r,L,R);
return ans;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
for(int i=1;i<=m;++i){
id=read();
if(id==1){
x=read(),y=read(),k=read();
update(1,1,n,x,y,k);
}
else{
x=read(),y=read();
write(query(1,1,n,x,y)),ed;
}
}
return 0;
}by 210101zhaosicheng @ 2024-07-09 10:37:42
@wanghx1
你的 pushdown 函数写错了，建议不要省那一点点代码量，直接再写一个函数，比如叫 ADD 用来处理加法。
为了查错，我把代码中的快读快写，还有一部分不必要的代码删去了，pushdown 的传入也有一点变化们可以仔细研究一下。
这里是代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1000500
#define int long long
int n,m,a[N],sum[N<<2],add[N<<2],id,x,y,k;
void pushup(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
if(l==r){
sum[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void pushdown(int rt,int ln,int rn){
if(add[rt]){
int mid=(ln+rn)>>1;//改动
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=add[rt]*(mid-ln+1);//改动
sum[rt<<1|1]+=add[rt]*(rn-mid);//改动
add[rt]=0;
}
}
void update(int rt,int l,int r,int L,int R,int c){
if(L<=l&&r<=R){
sum[rt]+=c*(r-l+1);
add[rt]+=c;
return ;
}
int mid=(l+r)>>1;
pushdown(rt,l,r);//改动
if(L<=mid) update(rt<<1,l,mid,L,R,c);
if(R>mid) update(rt<<1|1,mid+1,r,L,R,c);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R) return sum[rt];
int mid=(l+r)>>1;
pushdown(rt,l,r);//改动
int ans=0;
if(L<=mid) ans+=query(rt<<1,l,mid,L,R);
if(R>mid) ans+=query(rt<<1|1,mid+1,r,L,R);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=m;++i){
scanf("%lld",&id);
if(id==1){
scanf("%lld%lld%lld",&x,&y,&k);
update(1,1,n,x,y,k);
}
else{
scanf("%lld%lld",&x,&y);
cout<<query(1,1,n,x,y)<<'\n';
}
}
return 0;
}by wanghx1 @ 2024-07-09 10:48:28
@210101zhaosicheng 谢谢