你在线段树中查询色块总数的时候是否有判断重复色块?
正确代码:
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