jeffrey @ 2023-08-02 08:15:35
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int lazy[N],s[N],a[N];
int n,m;
void build(int p,int l,int r)
{
if(l==r)
{
s[p]=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
s[p]=s[p*2]+s[p*2+1];
}
int f(int p,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&qr>=r)
{
s[p]+=(r-l+1)*k;
lazy[p]+=k;
}
int mid=(l+r)/2;
if(lazy[p])
{
s[p*2]+=lazy[p]*(mid-l+1);lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
s[p*2+1]+=lazy[p]*(r-mid);lazy[p]=0;
}
if(ql<=mid) f(p*2,l,mid,ql,qr,k);
if(qr>mid) f(p*2+1,mid+1,r,ql,qr,k);
}
int sum(int p,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r)
{
return s[p];
}
int mid=(l+r)/2;
if(lazy[p])
{
s[p*2]+=lazy[p]*(mid-l+1);lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
s[p*2+1]+=lazy[p]*(r-mid);lazy[p]=0;
}
int ans=0;
if(ql<=mid) ans+=sum(p*2,l,mid,ql,qr);
if(qr>mid) ans+=sum(p*2+1,mid+1,r,ql,qr);
return ans;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,k;
cin>>x>>y>>k;
f(1,1,n,x,y,k);
}
else
{
int x,y;
cin>>x>>y;
cout<<sum(1,1,n,x,y)<<endl;
}
}
return 0;
}
by _luanyi_ @ 2023-08-02 08:25:25
if(ql<=l&&qr>=r)
{
s[p]+=(r-l+1)*k;
lazy[p]+=k;
return;//你没有return
}
by _luanyi_ @ 2023-08-02 08:26:34
以及f函数末尾没有push_up。
by _luanyi_ @ 2023-08-02 08:28:32
以及f的类型应当是void。
by 皎月半洒花 @ 2023-08-02 08:29:02
两个问题,都是在你的 f 函数,也即区间加里面:
返回值应为 void
类型,并且在第一个 if 里需要 return。
没有 push_up()
操作。你需要在本函数的最后维护线段树的父子关系,也即你代码中的:
s[p]=s[p*2]+s[p*2+1];
基于以上,修改后的 f 函数:
void f(int p,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&qr>=r)
{
s[p]+=(r-l+1)*k;
lazy[p]+=k;
return ;
}
int mid=(l+r)/2;
if(lazy[p])
{
s[p*2]+=lazy[p]*(mid-l+1);lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
s[p*2+1]+=lazy[p]*(r-mid);lazy[p]=0;
}
if(ql<=mid) f(p*2,l,mid,ql,qr,k);
if(qr>mid) f(p*2+1,mid+1,r,ql,qr,k);
s[p]=s[p*2]+s[p*2+1];
}
by _luanyi_ @ 2023-08-02 08:32:04
楼上正解
by jeffrey @ 2023-08-02 09:27:32
谢谢大佬,我AC了