大佬求助线段树 ask 代码更改正确原因
查看原帖
大佬求助线段树 ask 代码更改正确原因
375953
Lgx_Q楼主2022/8/15 19:22

之前交的错误代码


int ask(int p,int l,int r,int ql,int qr,int flag)
{
	if(ql<=l&&r<=qr)
	{
		if(flag==0)return sum[p];
		if(flag==1)return ksum[p];
	}
	pushdown(p,l,r);
	int mid=l+r>>1;
	int ans=0;
	if(ql<=mid)
	{
		ans+=ask(p*2,l,mid,ql,qr,flag);
		if(flag==1) //维护 ksum 的正确性
		{
			ans+=ask(p*2,l,mid,ql,qr,0)*max(0ll,qr-mid);
		}
	}
	if(mid<qr)
	{
		ans+=ask(p*2+1,mid+1,r,ql,qr,flag);
	}
	return ans;
}

改了注释的部分,就 ACAC 了:

int ask(int p,int l,int r,int ql,int qr,int flag)
{
	if(ql<=l&&r<=qr)
	{
		if(flag==0)return sum[p];
		if(flag==1)return ksum[p]+sum[p]*(qr-r);//维护 ksum 正确性
	}
	pushdown(p,l,r);
	int mid=l+r>>1;
	int ans=0;
	if(ql<=mid)
	{
		ans+=ask(p*2,l,mid,ql,qr,flag);
	}
	if(mid<qr)
	{
		ans+=ask(p*2+1,mid+1,r,ql,qr,flag);
	}
	return ans;
}
2022/8/15 19:22
加载中...