您的位置: 首页  >  文章  >  [DFS序+树状数组+nim游戏]BZOJ 2819 nim 题解

[DFS序+树状数组+nim游戏]BZOJ 2819 nim 题解

分类: 文章 • 2024-05-29 11:22:22

题目大意

给出一棵带点权的树，多组询问树上一条链上的所有点的点权作为nim游戏的初始石子数，问是否存在必胜策略，带修改。

N,Q≤500000N,Q\le500000

解题分析

如果看过我那篇上了两次又删了两次的 2017暑假集训日记的话 （虽然我觉得应该没人记得82695518），应该知道我对于这道题的无奈，时隔15个月我终于找出了Bug——读入不严谨……果然还是蒟蒻。

上张图表示我对这道题的……嗯，不知道怎么形容……

[DFS序+树状数组+nim游戏]BZOJ 2819 nim 题解

当时就是奔着nim游戏这个标签做的（那时热衷于划水），然后顺便学习了一下DFS序结合树状数组和线段树的许多有趣的操作（在此安利一个比较实用的Blog）。虽然基本都忘了，但是这个套路还是很明显的。单点修改树链询问。修改时修改子树到根节点距离，询问利用LCA解决，所以就是区间修改然后单点查询，我原先线段树应该常数卡不了，但是还是卡了。所以用树状数组（毕竟常数少）。

示例代码

题目传送门

树状数组

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500005
#define maxe 1000005
using namespace std;
int n,q,tot,k,len,a[maxn],c[maxn],son[maxe],nxt[maxe],lnk[maxn],dep[maxn],L[maxn],R[maxn],fa[maxn][20];
inline char nc(){
	static char buf[100000],*pa=buf,*pb=buf;
	return pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++;
}
inline void readi(int &x){
	x=0; char ch=nc();
	while ('0'>ch||ch>'9') ch=nc();
	while ('0'<=ch&&ch<='9') {x=x*10+ch-'0'; ch=nc();}
}
void _add(int x,int y){
	son[++tot]=y; nxt[tot]=lnk[x]; lnk[x]=tot;
}
void _init(){
	freopen("nim.in","r",stdin);
	freopen("nim.out","w",stdout);
	readi(n); tot=0; len=log2(n);
	memset(lnk,0,sizeof(lnk));
	for (int i=1;i<=n;i++) readi(a[i]);
	for (int i=1,x,y;i<n;i++){
		readi(x); readi(y); _add(x,y); _add(y,x);
	}
}
void _dfs(int x){
	L[x]=++k;
	for (int i=1;i<=len&&(1<<i)<=dep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int j=lnk[x];j;j=nxt[j])
		if (son[j]!=fa[x][0]){
			dep[son[j]]=dep[x]+1; fa[son[j]][0]=x;
			_dfs(son[j]);
		}
	R[x]=k;
}
void T_change(int x,int t){for (;x<=n;x+=(x&(-x))) c[x]^=t;}
int T_get(int x){
	int tem=0;
	for (;x;x-=(x&(-x))) tem^=c[x];
	return tem;
}
inline int _LCA(int x,int y){
	if (dep[x]>dep[y]) swap(x,y);
	for (int j=len;j>=0;j--) if (dep[x]<=dep[fa[y][j]]) y=fa[y][j];	if (x==y) return x;
	for (int j=len;j>=0;j--) if (fa[x][j]!=fa[y][j]) {x=fa[x][j]; y=fa[y][j];} return fa[x][0];
}
void _solve(){
	memset(fa,0,sizeof(fa));
	k=fa[1][0]=0; dep[1]=1; _dfs(1); readi(q);
	for (int i=1;i<=n;i++) {T_change(L[i],a[i]); T_change(R[i]+1,a[i]);}
	while (q--){ //下面这个while就是卡了1.25年的Bug
		char ch=nc(); while (ch!='Q'&&ch!='C') ch=nc(); int x,y; readi(x); readi(y);
		if (ch=='C') {T_change(L[x],a[x]^y); T_change(R[x]+1,a[x]^y); a[x]=y;}
		else {
			int tem=T_get(L[x])^T_get(L[y])^a[_LCA(x,y)];
			if (tem) printf("Yes\n"); else printf("No\n");
		}
	}
}
int main()
{
	_init();
	_solve();
	return 0;
}

线段树各位神犇看看还能优化什么……华丽T掉了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500005
#define maxe 1000005
using namespace std;
int n,q,tot,k,len,a[maxn],son[maxe],nxt[maxe],lnk[maxn],dep[maxn],tL[maxn],tR[maxn],fa[maxn][20];
struct Seg{
	int tL[maxn<<2],tR[maxn<<2],sum[maxn<<2],tg[maxn<<2];
	inline void Pushup(int x){sum[x]=sum[x<<1]^sum[x<<1|1];}
	inline void Addtag(int x,int tem){sum[x]^=((tR[x]-tL[x]+1)&1)*tem; tg[x]^=tem;}
	inline void Pushdown(int x){if (tg[x]){Addtag(x<<1,tg[x]); Addtag(x<<1|1,tg[x]);} tg[x]=0;}
	inline void Build(int x,int L,int R){
		tL[x]=L; tR[x]=R; sum[x]=tg[x]=0; if (L==R) return;
		int mid=L+(R-L>>1); Build(x<<1,L,mid); Build(x<<1|1,mid+1,R);
	}
	inline void Insert(int x,int L,int R,int tem){
		if (tL[x]>R||tR[x]<L) return; if (L<=tL[x]&&tR[x]<=R) {Addtag(x,tem); return;}
		int mid=tL[x]+(tR[x]-tL[x]>>1); Pushdown(x);
		if (R<=mid) Insert(x<<1,L,R,tem); else if (L>mid) Insert(x<<1|1,L,R,tem);
		else {Insert(x<<1,L,mid,tem); Insert(x<<1|1,mid+1,R,tem);} Pushup(x);
	}
	inline int Ask(int x,int L,int R){
		if (tL[x]>R||tR[x]<L) return 0; if (L<=tL[x]&&tR[x]<=R) return sum[x];
		int mid=tL[x]+(tR[x]-tL[x]>>1); Pushdown(x);
		if (R<=mid) return Ask(x<<1,L,R); else if (L>mid) return Ask(x<<1|1,L,R);
		else return Ask(x<<1,L,mid)^Ask(x<<1|1,mid+1,R);
	}
}T;
inline char nc(){
	static char buf[100000],*pa=buf,*pb=buf;
	return pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++;
}
inline void readi(int &x){
	x=0; char ch=nc();
	while ('0'>ch||ch>'9') ch=nc();
	while ('0'<=ch&&ch<='9') {x=x*10+ch-'0'; ch=nc();}
}
void _add(int x,int y){
	son[++tot]=y; nxt[tot]=lnk[x]; lnk[x]=tot;
}
void _init(){
	freopen("nim.in","r",stdin);
	freopen("nim1.out","w",stdout);
	readi(n); tot=0; len=log2(n);
	memset(lnk,0,sizeof(lnk));
	for (int i=1;i<=n;i++) readi(a[i]);
	for (int i=1,x,y;i<n;i++){
		readi(x); readi(y); _add(x,y); _add(y,x);
	}
}
void _dfs(int x){
	tL[x]=++k;
	for (int j=lnk[x];j;j=nxt[j])
		if (son[j]!=fa[x][0]){
			dep[son[j]]=dep[x]+1; fa[son[j]][0]=x;
			_dfs(son[j]);
		}
	tR[x]=k;
}
inline int _LCA(int x,int y){
	if (dep[x]>dep[y]) swap(x,y);
	for (int j=len;j>=0;j--) if (dep[x]<=dep[fa[y][j]]) y=fa[y][j];	if (x==y) return x;
	for (int j=len;j>=0;j--) if (fa[x][j]!=fa[y][j]) {x=fa[x][j]; y=fa[y][j];} return fa[x][0];
}
void _solve(){
	memset(fa,0,sizeof(fa));
	k=0; dep[1]=1; _dfs(1); readi(q); T.Build(1,1,n);
	for (int j=1;j<=len;j++)
		for (int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
	for (int i=1;i<=n;i++) T.Insert(1,tL[i],tR[i],a[i]);
	while (q--){
		char ch=nc(); while (ch!='C'&&ch!='Q') ch=nc(); int x,y; readi(x); readi(y);
		if (ch=='C') {T.Insert(1,tL[x],tR[x],a[x]^y); a[x]=y;}
		else if (T.Ask(1,tL[x],tL[x])^T.Ask(1,tL[y],tL[y])^a[_LCA(x,y)]) printf("Yes\n"); else printf("No\n");
	}
}
int main()
{
	_init();
	_solve();
	return 0;
}

相关推荐