DengDuck @ 2022-11-08 21:49:03
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],op,x,y,k,sum[1000005],la[400005];
void build(long long pos,long long l,long long r)
{
if(l==r)
{
sum[pos]=a[l];
//cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
return;
}
long long mid=(l+r)/2;
build(pos*2,l,mid);
build(pos*2+1,mid+1,r);
sum[pos]=sum[pos*2]+sum[pos*2+1];
// cout<<pos<<' '<<l<<' '<<r<<' '<<sum[pos]<<endl;
}
void down(long long pos,long long l,long long r)
{
la[pos*2]+=la[pos];
la[pos*2+1]+=la[pos];
la[pos]=0;
long long mid=(l+r)/2;
sum[pos*2]+=la[pos*2]*(mid-l+1);
sum[pos*2+1]+=la[pos*2+1]*(r-mid);
sum[pos]=sum[pos*2]+sum[pos*2+1];
}
void add(long long pos,long long l,long long r,long long el,long long er,long long k)
{
if(r<el||er<l)return;
if(el<=l&&r<=er)
{
sum[pos]+=k*(r-l+1);
la[pos]+=k;
return;
}
down(pos,l,r);
long long mid=(l+r)/2;
add(pos*2,l,mid,el,er,k);
add(pos*2+1,mid+1,r,el,er,k);
sum[pos]=sum[pos*2]+sum[pos*2+1];
}
long long query(long long pos,long long l,long long r,long long el,long long er)
{
if(r<el||er<l)return 0;
if(el<=l&&r<=er)
{
// cout<<pos<<' '<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<sum[pos]<<endl;
return sum[pos];
}
down(pos,l,r);
long long mid=(l+r)/2;
//cout<<pos<<l<<' '<<r<<' '<<el<<' '<<er<<' '<<query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er)<<endl;
return query(pos*2,l,mid,el,er)+query(pos*2+1,mid+1,r,el,er);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(1,1,n,x,y,k);
}
if(op==2)
{
cin>>x>>y;
cout<<query(1,1,n,x,y)<<endl;
}
}
}
by vvauted @ 2022-11-08 21:50:04
@DengDuck down 写错了,建议看看题解
by Asimplename @ 2022-11-08 21:52:09
您这么写 PushDown 应该是错的,应该是子节点都更新完了才往上更新吧(?