rome_empire @ 2022-12-01 01:37:40
求助各位大佬,为啥我只对了第一个点QAQ
#include<bits/stdc++.h>
#define ls (x*2)
#define rs (x*2+1)
using namespace std;
long long sumn[400005],a[400005],tag[400005];
void update(int x)
{
sumn[x]=sumn[x*2]+sumn[x*2+1];
}
void build(int l,int r,int x)
{
if(l==r)
{
sumn[x]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
update(x);
}
void down(int l,int r,int x)
{
int mid=(l+r)>>1;
if(tag[x]>0)
{
tag[ls]=tag[rs]=tag[x];
sumn[ls]+=(mid-l+1)*tag[x];
sumn[rs]+=(r-mid-1+1)*tag[x];
tag[x]=0;
}
}
long long query(int A,int B,int l,int r,int x)
{
if(A<=l && r<=B)
{
return sumn[x];
}
down(l,r,x);
int mid=(l+r)>>1;
long long ans=0;
if(A<=mid)
{
ans=ans+query(A,B,l,mid,x*2);
}
if(mid<B)
{
ans=ans+query(A,B,mid+1,r,x*2+1);
}
return ans;
}
void change(int A,int B,int v,int l,int r,int x)
{
if(A<=l && r<=B)
{
tag[x]=v;
sumn[x]+=v*(r-l+1);
return;
}
down(l,r,x);
int mid=(l+r)>>1;
if(A<=mid) change(A,B,v,l,mid,ls);
if(mid<B) change(A,B,v,mid+1,r,rs);
update(x);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
int x,y,z;
int c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=m;i++)
{
cin>>c;
if(c==1)
{
cin>>x>>y>>z;
change(x,y,z,1,n,1);
}
if(c==2)
{
cin>>x>>y;
cout<<query(x,y,1,n,1)<<endl;
}
}
}
by rome_empire @ 2022-12-01 01:38:15
please
by VictorChen @ 2022-12-01 03:29:10
tag[ls] = tag[rs] = tag[x];
应改为
tag[ls] += tag[x];
tag[rs] += tag[x];
因为可能当时的子节点内已经存在lazy了;
by DYYqwq @ 2022-12-01 07:36:47
@VictorChen 可能需要4倍空间吧,线段树都这样
by Xeqwq @ 2022-12-01 07:41:29
@DongYUyao 四倍开了
by DYYqwq @ 2022-12-01 07:42:09
@Xeqwq (艹,我没看题
by DYYqwq @ 2022-12-01 07:45:23
@rome_empire 我发现开到600005就行了(
by rome_empire @ 2022-12-02 00:00:13
@VictorChen 谢谢了orz
刚学线段树,积累经验ing
by rome_empire @ 2022-12-02 00:00:38
@DongYUyao 我 try try
by rome_empire @ 2022-12-02 00:01:04
@DongYUyao 这个不假