关于树剖的单点修改
查看原帖
关于树剖的单点修改
257206
Herio楼主2021/4/6 15:15

为什么单点修改也要下放标记?

void upd1(int x,int p,int v){
	if(a[x].l==a[x].r){
		a[x].s+=v;
		return;
	}
	int m=(a[x].l+a[x].r)>>1;
	if(p<=m) upd1(lx,p,v);
	else upd1(rx,p,v);
	re(x);
}

上面这样写会全WA, 下面这样下会AC

void upd1(int x,int p,int v){
	if(a[x].l==a[x].r){
		a[x].s+=v;
		a[x].lz+=v;return;
	}
	pushdown(x);
	int m=(a[x].l+a[x].r)>>1;
	if(p<=m) upd1(lx,p,v);
	else upd1(rx,p,v);
	re(x);
}
2021/4/6 15:15
加载中...