【XSY3679】农民（树链剖分）

题面

题解

先考虑一个节点怎么样才会被走到。

对于一个权值为为 \(x\) 的节点，它的左子树内的节点有可能被走到仅当其权值小于 \(x\)，右子树内的节点有可能被走到仅当其权值大于 \(x\)。

那么树上每条边相当于给这条边以下的子树加了一个大于或是小于的限制，询问一个节点时，只要判断这个节点的权值是否同时满足到根路径上所有边的限制即可。

我们可以用树链剖分加线段树维护这个限制，单点修改很好处理，子树翻转相当于取反子树内所有限制的符号，线段树同时维护一下翻转后的限制，打标记维护即可。时间复杂度 \(O(m\log ^2 n)\)。

#include<bits/stdc++.h>

#define N 100010
#define INF 0x7fffffff

using namespace std;

struct Part
{
	int minn,maxn;
	Part(){minn=-INF,maxn=INF;}
	Part(int l,int r){minn=l,maxn=r;}
}p[N<<2][2];

Part operator + (Part a,Part b)
{
	return Part(max(a.minn,b.minn),min(a.maxn,b.maxn));
}

int n,m,rt,a[N];
int tot,ch[N][2],from[N],fa[N],size[N],son[N],dep[N],top[N],id[N],rk[N];
int ffrom[N<<2];
bool now[N<<2],rev[N<<2];
//maxn[u][0]未翻转最大值，minn[u][0]未翻转最小值
//maxn[u][1]翻转后最大值，minn[u][0]翻转后最小值

void dfs(int u)
{
	size[u]=1;
	for(int i=0;i<2;i++)
	{
		int v=ch[u][i];
		if(!v) continue;
		dep[v]=dep[u]+1;
		dfs(v);
		size[u]+=size[v];
		if(size[v]>size[son[u]]) son[u]=v;
	}
}

void dfs1(int u,int tp)
{
	top[u]=tp;
	id[u]=++tot;
	rk[tot]=u;
	if(son[u]) dfs1(son[u],tp);
	for(int i=0;i<2;i++)
		if(ch[u][i]&&ch[u][i]!=son[u])
			dfs1(ch[u][i],ch[u][i]);
}

void calc(int k,int l)
{
	int u=rk[l],f=fa[u];
	if(u==rt)
	{
		p[k][0]=p[k][1]=Part(-INF,INF);
		return;
	}
	if(!ffrom[k])
	{
		p[k][0]=Part(-INF,a[f]-1);
		p[k][1]=Part(a[f]+1,INF);
	}
	else
	{
		p[k][0]=Part(a[f]+1,INF);
		p[k][1]=Part(-INF,a[f]-1);
	}
}

void up(int k)
{
	p[k][0]=p[k<<1][0]+p[k<<1|1][0];
	p[k][1]=p[k<<1][1]+p[k<<1|1][1];
}

void downn(int k)
{
	swap(p[k][0],p[k][1]);
	ffrom[k]^=1,rev[k]^=1;
}

void down(int k)
{
	if(rev[k])
	{
		downn(k<<1),downn(k<<1|1);
		rev[k]=0;
	}
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		ffrom[k]=from[rk[l]];
		calc(k,l);
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	up(k);
}

void update(int k,int l,int r,int x)
{
	if(l==r)
	{
		calc(k,l);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(k<<1,l,mid,x);
	else update(k<<1|1,mid+1,r,x);
	up(k);
}

void make_tag(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
	{
		downn(k);
		return;
	}
	down(k);
	int mid=(l+r)>>1;
	if(ql<=mid) make_tag(k<<1,l,mid,ql,qr);
	if(qr>mid) make_tag(k<<1|1,mid+1,r,ql,qr);
	up(k);
}

Part query(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return p[k][now[k]];
	down(k);
	int mid=(l+r)>>1;
	Part ans;
	if(ql<=mid) ans=ans+query(k<<1,l,mid,ql,qr);
	if(qr>mid) ans=ans+query(k<<1|1,mid+1,r,ql,qr);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		for(int j=0;j<2;j++)
		{
			scanf("%d",&ch[i][j]);
			fa[ch[i][j]]=i,from[ch[i][j]]=j;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!fa[i])
		{
			rt=i;
			break;
		}
	}
	dfs(rt),dfs1(rt,rt);
	build(1,1,n);
	while(m--)
	{
		int opt,u;
		scanf("%d%d",&opt,&u);
		if(opt==1)
		{
			scanf("%d",&a[u]);
			for(int i=0;i<2;i++)
			{
				int v=ch[u][i];
				if(v) update(1,1,n,id[v]);
			}
		}
		if(opt==2)
		{
			for(int i=0;i<2;i++)
			{
				int v=ch[u][i];
				if(v) make_tag(1,1,n,id[v],id[v]+size[v]-1);
			}
		}
		if(opt==3)
		{
			Part ans;
			int now=u;
			while(now)
			{
				ans=ans+query(1,1,n,id[top[now]],id[now]);
				now=fa[top[now]];
			}
			if(ans.minn<=a[u]&&a[u]<=ans.maxn) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}
/*
3 7
10 2 3
5 0 0
5 0 0
3 1
3 2
3 3
1 3 100
3 3
2 1
3 3
*/