byft @ 2023-11-03 13:18:18
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1919810],dp[1919810],dp_[1919810];
void build(int l,int r,int f)
{
if(l==r)
{dp[f]=a[l];return;}
int mid=l+r>>1;
build(l,mid,f<<1);
build(mid+1,r,f<<1|1);
dp[f]=dp[f<<1]+dp[f<<1|1];
}
int plus_(int l,int r,int start,int end,int f)
{
if(l<=start && r>=end)
return dp[f];
int mid=start+end>>1,ans=0;
if(dp_[f])
{
dp[f<<1]+=dp_[f]*(mid-start+1),dp[f<<1|1]+=dp_[f]*(end-mid);
dp_[f<<1]+=dp_[f],dp_[f<<1|1]+=dp_[f];
dp_[f]=0;
}
if(l<=mid) ans+=plus_(l,r,start,mid,f<<1);
if(r>mid) ans+=plus_(l,r,mid+1,end,f<<1|1);
return ans;
}
void update(int l,int r,int add,int start,int end,int f)
{
if(l<=start && end<=r)
{dp[f]+=(end-start+1)*add;dp_[f]+=add;return;}
int mid=start+end>>1;
if(dp_[f] && start!=end)
{
dp[f<<1]+=dp_[f]*(mid-start+1),dp[f<<1|1]+=dp_[f]*(end-mid);
dp_[f<<1]+=dp_[f],dp[f<<1|1]+=dp_[f];
dp_[f]=0;
}
if(l<=mid) update(l,r,add,start,mid,f<<1);
if(r>mid) update(l,r,add,mid+1,end,f<<1|1);
dp[f]=dp[f<<1]+dp[f<<1|1];
}
signed main()
{
int n,m;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,n,1);
while(m--)
{
int op;
scanf("%lld",&op);
if(op==1)
{
int l,r,add;
scanf("%lld %lld %lld",&l,&r,&add);
update(l,r,add,1,n,1);
}
else
{
int l,r,add;
scanf("%lld %lld",&l,&r);
printf("%lld\n",plus_(l,r,1,n,1));
}
}
return 0;
}如果发现错误，请告诉我在哪个函数里的，谢谢！（悬棺
by lishunji @ 2023-11-03 13:41:31
先参考一下，在机房没时间改了，今晚我帮你看看（
#include<bits/stdc++.h>
using namespace std;
struct node{long long O;}o;
long long n,m,ans,a[1000010],add[4000010],sum[4000010];
void maketree(long long k,long long l,long long r){
if(l==r){
sum[k]=a[l];
return;
}
long long mid=(l+r)>>1;
maketree(k*2,l,mid);
maketree(k*2+1,mid+1,r);
sum[k]=sum[k*2]+sum[k*2+1];
}
void Add(long long k,long long l,long long r,long long v){
add[k]+=v;
sum[k]+=(r-l+1)*v;
return ;
}
void pushdown(long long k,long long l,long long r,long long mid){
if(add[k]==0) return ;
Add(k*2,l,mid,add[k]);
Add(k*2+1,mid+1,r,add[k]);
add[k]=0;
}
void updata(long long k,long long l,long long r,long long x,long long y,long long v){
if(x<=l&&r<=y){
Add(k,l,r,v);
return ;
}
if(r<x||y<l) return ;
if(l==r) return ;
long long mid=(l+r)>>1;
pushdown(k,l,r,mid);
updata(k*2,l,mid,x,y,v);
updata(k*2+1,mid+1,r,x,y,v);//
sum[k]=sum[k*2]+sum[k*2+1];
}
long long que(long long k,long long l,long long r,long long x,long long y){
if(r<x||y<l) return 0;
if(x<=l&&r<=y) return sum[k];
long long mid=(l+r)>>1;
pushdown(k,l,r,mid);
return (que(k*2,l,mid,x,y)+que(k*2+1,mid+1,r,x,y));
}
int main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
maketree(1,1,n);
for(long long i=1;i<=m;i++){
long long x,y,k;
scanf("%lld",&o.O);
if(o.O==1){
scanf("%lld%lld%lld",&x,&y,&k);
updata(1,1,n,x,y,k);
}
else{
scanf("%lld%lld",&x,&y);
printf("%lld\n",que(1,1,n,x,y));
}
}
return 0;
}by Eltaos_xingyu @ 2023-11-03 13:52:16
额......
您的代码有个地方写挂了...
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define int long long
int a[1919810],dp[1919810],dp_[1919810];
void build(int l,int r,int f)
{
if(l==r)
{dp[f]=a[l];return;}
int mid=l+r>>1;
build(l,mid,f<<1);
build(mid+1,r,f<<1|1);
dp[f]=dp[f<<1]+dp[f<<1|1];
}
int plus_(int l,int r,int start,int end,int f)
{
if(l<=start && r>=end)
return dp[f];
int mid=start+end>>1,ans=0;
if(dp_[f])
{
dp[f<<1]+=dp_[f]*(mid-start+1),dp[f<<1|1]+=dp_[f]*(end-mid);
dp_[f<<1]+=dp_[f],dp_[f<<1|1]+=dp_[f];
dp_[f]=0;
}
if(l<=mid) ans+=plus_(l,r,start,mid,f<<1);
if(r>mid) ans+=plus_(l,r,mid+1,end,f<<1|1);
return ans;
}
void update(int l,int r,int add,int start,int end,int f)
{
if(l<=start && end<=r)
{dp[f]+=(end-start+1)*add;dp_[f]+=add;return;}
int mid=start+end>>1;
if(dp_[f] && start!=end)
{
dp[f<<1]+=dp_[f]*(mid-start+1),dp[f<<1|1]+=dp_[f]*(end-mid);
dp_[f<<1]+=dp_[f],dp_[f<<1|1]+=dp_[f];//这里
dp_[f]=0;
}
if(l<=mid) update(l,r,add,start,mid,f<<1);
if(r>mid) update(l,r,add,mid+1,end,f<<1|1);
dp[f]=dp[f<<1]+dp[f<<1|1];
}
signed main()
{
int n,m;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,n,1);
while(m--)
{
int op;
scanf("%lld",&op);
if(op==1)
{
int l,r,add;
scanf("%lld %lld %lld",&l,&r,&add);
update(l,r,add,1,n,1);
}
else
{
int l,r,add;
scanf("%lld %lld",&l,&r);
printf("%lld\n",plus_(l,r,1,n,1));
}
}
return 0;
}@byft
by Eltaos_xingyu @ 2023-11-03 13:53:55
确实不容易一眼看出来，建议标记数组和线段树数组的名字尽量不要过于相同。
by byft @ 2023-11-03 14:00:14
@Eltaos_xingyu 所以应该改成什么样呢
by Eltaos_xingyu @ 2023-11-03 14:04:09
@byft
by Eltaos_xingyu @ 2023-11-03 14:05:00
发出来的代码里已经给你改了。
void update(int l,int r,int add,int start,int end,int f)
{
if(l<=start && end<=r)
{dp[f]+=(end-start+1)*add;dp_[f]+=add;return;}
int mid=start+end>>1;
if(dp_[f] && start!=end)
{
dp[f<<1]+=dp_[f]*(mid-start+1),dp[f<<1|1]+=dp_[f]*(end-mid);
dp_[f<<1]+=dp_[f],dp_[f<<1|1]+=dp_[f];//这里，你原来是dp[f<<1|1]+=dp_[f]
dp_[f]=0;
}
if(l<=mid) update(l,r,add,start,mid,f<<1);
if(r>mid) update(l,r,add,mid+1,end,f<<1|1);
dp[f]=dp[f<<1]+dp[f<<1|1];
}by byft @ 2023-11-03 14:05:54
@Eltaos_xingyu 谢谢，已关