BZOJ_3729_Gty的游戏_博弈论+splay+dfs序

Description

某一天gty在与他的妹子玩游戏。
妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问
将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。
gty很快计算出了策略。
但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。
gty不忍心打击妹子，所以他将这个问题交给了你。
另外由于gty十分绅士，所以他将先手让给了妹子。

Input

第一行两个数字，n和L,n<=5*10^4,L<=10^9
第二行n个数字，表示每个节点初始石子数。
接下来n-1行，每行两个整数u和v，表示有一条从u到v的边。
接下来一行一个数m，表示m组操作。
接下来m行，每行第一个数字表示操作类型
若为1，后跟一个数字v，表示询问在v的子树中做游戏先手是否必胜。
若为2，后跟两个数字x，y表示将节点x的石子数修改为y。
若为3，后跟三个数字u,v,x，表示为u节点添加一个儿子v，初始石子数为x。
在任意时刻，节点数不超过5*10^4。

Output

对于每个询问，若先手必胜，输出"MeiZ",否则输出"GTY"。
另，数据进行了强制在线处理，对于m组操作，除了类型名以外，都需要异或之前回答为"MeiZ"的个数。

Sample Input

2 1000
0 0
1 2
1
1 1

Sample Output

GTY

阶梯Nim博弈，和根节点层数奇偶相同的层可以当做没有。

因为对于每个由奇变偶的石子，都可以再由偶变奇，相当于偶数层的没有用。

同时每次最多取L个，相当于这样一个问题：

求奇数层上所有石子%(L+1)的异或和。

splay维护一下。

一开始以为只需要维护出栈序，然后发现插入不太好插。于是维护出栈入栈序。

插入直接插两个点。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 400050

#define ls ch[p][0]

#define rs ch[p][1]

#define get(x) (ch[f[x]][1]==x)

int ch[N][2],f[N],sum[N],s1[N],s2[N];

int head[N],to[N<<1],nxt[N<<1],cnt,n,L,rt,dfn[N],val[N],a[N],son[N],m,w[N],dep[N],D[N],sz;

inline void add(int u,int v) {

	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

void pushup(int p) {

	if(!p) return ;

	// s2[p]=val[p]; s1[p]=0;

	if(D[p]&1) s1[p]=val[p],s2[p]=0;

	else s1[p]=0,s2[p]=val[p];

	// if(ls) s2[p]=(s2[p]+s1[ls])%L,s1[p]=(s1[p]+s2[ls])%L;

	// if(rs) s2[p]=(s2[p]+s1[rs])%L,s1[p]=(s1[p]+s2[rs])%L;

	if(ls) s2[p]^=s2[ls],s1[p]^=s1[ls];

	if(rs) s2[p]^=s2[rs],s1[p]^=s1[rs];

}

void rotate(int x) {

	int y=f[x],z=f[y],k=get(x);

	ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;

	ch[x][!k]=y; f[y]=x; f[x]=z;

	if(z) ch[z][ch[z][1]==y]=x;

	if(rt==y) rt=x;

	pushup(y); pushup(x);

}

void splay(int x,int y) {

	for(int d;(d=f[x])!=y;rotate(x))

		if(f[d]!=y)

			rotate(get(x)==get(d)?d:x);

}

void dfs(int x,int y) {

	int i;

	dfn[x]=++sz; a[sz]=w[x]; D[sz]=dep[x];

	for(i=head[x];i;i=nxt[i]) {

		if(to[i]!=y) {

			dep[to[i]]=dep[x]+1;

			dfs(to[i],x);

		}

	}

	son[x]=++sz;

}

void build(int l,int r,int fa) {

	if(l>r) return  ;

	int mid=(l+r)>>1;

	f[mid]=fa; ch[fa][mid>fa]=mid;

	val[mid]=a[mid];

	build(l,mid-1,mid);

	build(mid+1,r,mid);

	pushup(mid);

}

int suc() {

	int p=ch[rt][1];

	while(ls) p=ls;

	return p;

}

int main() {

	scanf("%d%d",&n,&L); L++;

	int i,x,y;

	for(i=1;i<=n;i++) scanf("%d",&w[i]),w[i]%=L;

	for(i=1;i<n;i++) {

		scanf("%d%d",&x,&y); add(x,y); add(y,x);

	}

	dep[1]=1;

	sz++;

	dfs(1,0);

	sz++;

	build(1,sz,0);

	rt=(sz+1)>>1;

	scanf("%d",&m);

	int opt,z;

	int ans=0;

	while(m--) {

		scanf("%d%d",&opt,&x);

		x^=ans;

		// printf("%d\n",opt);

		if(opt==1) {

			// printf("%d %d\n",m,x);

			// printf("%d %d\n",dfn[x],son[x]);

			// printf("%d %d\n",dfn[x],rt);

			splay(dfn[x],0);

			// printf("%d %d\n",dfn[x],rt);

			if(dfn[x]!=rt) {puts("FUCK"); break;} splay(son[x],dfn[x]);

			int re=(dep[x]&1)?s2[ch[son[x]][0]]:s1[ch[son[x]][0]];

			if(re) ans++,puts("MeiZ");

			else {puts("GTY");}

		}else if(opt==2) {

			scanf("%d",&y); y^=ans;

			// val[dfn[x]]=y%L; for(i=dfn[x];i;i=f[i]) pushup(i);

			splay(dfn[x],0); val[dfn[x]]=y%L; pushup(dfn[x]);

		}else if(opt==3) {

			scanf("%d%d",&y,&z); y^=ans; z^=ans;

			dep[y]=dep[x]+1;

			splay(dfn[x],0);

			int p=suc();

			splay(p,rt);

			dfn[y]=++sz; son[y]=++sz; val[dfn[y]]=z%L;

			f[dfn[y]]=p; ls=dfn[y]; f[son[y]]=dfn[y]; ch[dfn[y]][1]=son[y];

			D[dfn[y]]=dep[y];

			pushup(son[y]); pushup(dfn[y]); pushup(p); pushup(rt);

		}

	}

}

巴特西