黑白树 做题记录

给定一棵 $n$ 个点的有根树，每个点有黑白颜色和点权。进行 $Q$ 次操作，每次操作是以下五种中的一种：

• 反转一个点的颜色；
• 将一个点所在的同色连通块中点的点权增加；
• 查询一个点所在的同色连通块中点的点权最大值；
• 将两个点之间的路径的点权增加；
• 将一个子树内点的点权增加；

$1\le N,Q\le2\times10^5$。

最后两个操作似乎让我们只能树剖+线段树，即 dfs 序上的区间操作。

同色联通块这个限制很麻烦，但是不难发现一个联通块相当于最浅的点的子树挖掉一些不属于该联通块的子树，体现在 dfs 序上就是一个大区间挖掉一些极长的小区间。

注意到黑白联通块可以分开做，下面来考虑对黑联通块的操作。

那么考虑在线段树上找到被挖掉的这些小区间。对于线段树的上一个节点 $[l,r]$，设其父亲为 $[l_{fa},r_{fa}]$，则若存在某个白点对应的区间 $[L,R]$ 满足 $[l,r]\subseteq[L,R]$ 且 $[l_{fa},r_{fa}]\not\subseteq[L,R]$，则可以给节点 $[l,r]$ 打一个 “被挖掉” 的 tag。也即将每个白点在线段树上拆分出的 $\log$ 个极长区间打上该 tag。

这样线段树上一个点 $u$ 的儿子若有“被挖掉”的 tag，那么这个儿子区间中的点就不属于 $u$ 对应的黑联通块。

所以在做各种线段树操作的时候判断一下儿子是否被挖掉即可。

查询的时候查询联通块中最浅黑点的区间即可，注意在找其拆分出的 $\log$ 个极长区间的时候不需要管这个“被挖掉”的 tag。

其实这个“被挖掉”的 tag 相当于将“取消被 $\subseteq[L,R]$ 的白区间覆盖的点的贡献”这个操作提前了，融入进普通线段树操作中。

可以结合代码理解：

const int S=100005,inf=1e8;

int a[S];
int mx[S<<2],tag[S<<2];
bool del[S<<2];

void dellr(int u,int l,int r,int L,int R) // 先给白点拆出来的区间打标记
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R) return del[u]=true,void();
	int mid=l+r>>1;
	if(L<=mid) dellr(u<<1,l,mid,L,R);
	if(R>=mid+1) dellr(u<<1|1,mid+1,r,L,R);
}

inline void upda(int u)
{
	mx[u]=-inf;
	if(!del[u<<1]) mx[u]=max(mx[u],mx[u<<1]);
	if(!del[u<<1|1]) mx[u]=max(mx[u],mx[u<<1|1]);
}

inline void addtag(int u,int x){mx[u]+=x,tag[u]+=x;}

inline void dwntag(int u)
{
	if(tag[u]==0) return;
	if(!del[u<<1]) addtag(u<<1,tag[u]);
	if(!del[u<<1|1]) addtag(u<<1|1,tag[u]);
	tag[u]=0;
}

void addlr(int u,int l,int r,int L,int R,int x) // 修改 [L,R] 所在的黑点联通块
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R)
	{
		if(!del[u]) addtag(u,x);
		return;
	}
	dwntag(u);
	int mid=l+r>>1;
	if(L<=mid) addlr(u<<1,l,mid,L,R,x);
	if(R>=mid+1) addlr(u<<1|1,mid+1,r,L,R,x);
	upda(u);
}

void quelr(int u,int l,int r,int L,int R,int &res) // 查询 [L,R] 所在的黑点联通块
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R)
	{
		if(!del[u]) res=max(res,mx[u]);
		return;
	}
	dwntag(u);
	int mid=l+r>>1;
	if(L<=mid) quelr(u<<1,l,mid,L,R,res);
	if(R>=mid+1) quelr(u<<1|1,mid+1,r,L,R,res);
}

加上颜色反转操作无非是额外计算每个节点被“挖掉”了几次以便支持将白点变黑，注意一定要先 downtag 再修改。

这个东西实际上很强大，但是现在似乎没什么对应的题目。