警示树剖全WA的后人
查看原帖
警示树剖全WA的后人
225375
Cuxhin楼主2024/9/3 15:32

你在线段树中查询色块总数的时候是否有判断重复色块?

正确代码:

int query_sum(int p,int l,int r){
	if(t[p].r<l or t[p].l>r) return 0;
	if(l<=t[p].l and t[p].r<=r){
		if(t[p].l==l) pre_lc=t[p].lc;
		if(t[p].r==r) pre_rc=t[p].rc;
		return t[p].sum;
	}
	push_down(p);
	//下面
	int lsum=query_sum(lson,l,r);
	int rsum=query_sum(rson,l,r);
	if(lsum and rsum and t[lson].rc==t[rson].lc){
		return lsum+rsum-1;
	}
	return lsum+rsum;
}

错误代码:


int query_sum(int p,int l,int r){
	if(t[p].r<l or t[p].l>r) return 0;
	if(l<=t[p].l and t[p].r<=r){
		if(t[p].l==l) pre_lc=t[p].lc;
		if(t[p].r==r) pre_rc=t[p].rc;
		return t[p].sum;
	}
	push_down(p);
	//下面
	return query_sum(lson,l,r)+query_sum(rson,l,r);
}

我连树剖的时候不同链之间判重我都不看题解做到了,这个这么基本的都没做到。。大家一定要打好基本盘,注意细节啊QAQ

2024/9/3 15:32
加载中...