关于LCT的lazytag
查看原帖
关于LCT的lazytag
109634
Cyber_Tree楼主2021/7/9 21:41

如果LCT的lazy tag表示的是该节点已经操作过但是没有下传,就可以过,如下:


inline void push_rev(int p) { r[p]^=1, _swap(son[p][1], son[p][0]); }
inline void push_lz(int p){
	lz[p]^=1; _swap(maxn[p], minn[p]);
	maxn[p]=-maxn[p], minn[p]=-minn[p], a[p]=-a[p];
}
inline void pushdown(int p){
	if(r[p]) r[p]=0, push_rev(son[p][1]), push_rev(son[p][0]);
	if(lz[p]) lz[p]=0, push_lz(son[p][1]), push_lz(son[p][0]);
}

但是如果表示当前节点没有操作也没有下传就会惨挂。。。。如下:

inline void pushdown(int p){
	if(r[p]){
		_swap(son[p][0], son[p][1]);
		r[p]=0; r[son[p][1]]^=1, r[son[p][0]]^=1;
	}
	if(lz[p]){
		_swap(maxn[p], minn[p]);
		maxn[p]=-maxn[p]; minn[p]=-minn[p]; a[p]=-a[p];
		lz[p]=0; lz[son[p][1]]^=1, lz[son[p][0]]^=1;
	}
	upd(p);
}

本蒟蒻并不明白这两种方式有什么实质性差别。。。
求助大佬。。。

2021/7/9 21:41
加载中...