警钟敲烂:9pts的一种原因
查看原帖
警钟敲烂:9pts的一种原因
754467
f_hxr_楼主2024/1/9 16:02

区间查询必须要打包成一个结构体,然后老老实实合并,就像这样:

node query(int p,int L,int R,int ql,int qr){
	if(ql<=L&&R<=qr)return dat[p];
	pushdown(dat[p]);int mid=(L+R)>>1;
	if(ql<=mid&&mid+1<=qr){
		node ret,LHQ=query(dat[p].ls,L,mid,ql,qr),RMJ=query(dat[p].rs,mid+1,R,ql,qr);
		ret.sum=LHQ.sum+RMJ.sum;
		ret.lmax=max(LHQ.lmax,LHQ.sum+RMJ.lmax);
		ret.rmax=max(RMJ.rmax,RMJ.sum+LHQ.rmax);
		ret.ans=max(max(LHQ.ans,RMJ.ans),LHQ.rmax+RMJ.lmax);
		return ret;	
	}
	if(ql<=mid)return query(dat[p].ls,L,mid,ql,qr);
	if(mid+1<=qr)return query(dat[p].rs,mid+1,R,ql,qr);
}

不要像这样偷懒:直接套个rmax[ls[p]]+lmax[rs[p]]没错我因此重构了整个代码调了1h

int QueryRange(int p,int L,int R,int ql,int qr){
	if(ql<=L&&R<=qr)return ans[p];
	pushdown(p);int mid=(L+R)>>1;
	if(ql<=mid&&mid+1<=qr)
		return max(max(QueryRange(ls[p],L,mid,ql,qr),
		   			   QueryRange(rs[p],mid+1,R,ql,qr)),
					   rmax[ls[p]]+lmax[rs[p]]);
	if(ql<=mid)return QueryRange(ls[p],L,mid,ql,qr);
	if(mid+1<=qr)return QueryRange(rs[p],mid+1,R,ql,qr);
}
2024/1/9 16:02
加载中...