给一个可能有很多人犯的错误
查看原帖
给一个可能有很多人犯的错误
1121518
StarsIntoSea楼主2025/7/31 15:12

如果你用可持久化线段树+标记永久化,如果你只在最后区间覆盖的时候再更新和打标记,像写普通线段树一样:

void update(int x,int &y,int l,int r,int L,int R,int k){
	y=++tot;
	lc[y]=lc[x],rc[y]=rc[x],t[y]=t[x],tag[y]=tag[x];
	if(L<=l && r<=R){
		t[x]+=(ll)(r-l+1)*k;
		tag[y]+=(ll)k;
		return ;
	}
	if(L<=mid) update(lc[x],lc[y],l,mid,L,R,k);
	if(R>mid) update(rc[x],rc[y],mid+1,r,L,R,k);
	pushup(y);
}

这样做错误的原因是,被打标记的这个节点的所有子孙,因受标记永久化的影响没有被更改。导致在下次修改时,如果访问到这些点,因为这些点没有被及时更新,导致把一个没有及时更新的点上传,就会出错。

比如在更新区间 [1,2] 时: 蓝色的部分就因为标记而没有修改。

如果这时候再更新区间 [2,4]:

就会把没有更新的位置 2 带上去,就会出错。

正确的更新应该是遍历一个点就更新,或者带着标记更新。

2025/7/31 15:12
加载中...