BZOJ 3729 GTY的游戏

BZOJ 3729 GTY的游戏

伪ETT？

貌似就是Splay维护dfn = =

我们首先观察这个博弈

这个博弈直接%(l+1)应该还是很显然的 因为先手怎么操作后手一定能保证操作总数取到(l+1)

于是就变成阶梯Nim了 因为对于先手从深度奇数点挪到深度偶数点后手接着可以把它挪回深度偶数点 所以就是典型的阶梯Nim

我们可以发现 只需要维护子树到一个点深度差为奇数的点的异或和就可以了

这个操作显然可以对整棵树按深度黑白染色 分别维护奇数层&偶数层即可（我这里用的是总和和奇数和

对于添加一个点那么我们直接把它挂到父亲后面就可以了 因为子树顺序对答案没有影响

然后调起来有点烦 这里学习到一个新的套路 就是新建一个Null节点 满足所有的边界条件 把它放在最后 这样就可以避免死循环的情况= =

然后这个思博样例显然没有卵用 需要自己造数据 然后我忘了要异或^mz 于是造出一堆不合法数据在那调 xtbl

写起来其实挺短的 和ETT没毛关系的样子。

//Love and Freedom.
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define ll long long
#define inf 20021225
#define N 100001
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define Null N-1
using namespace std;
int read()
{int s=0,f=1; char ch=getchar();while(ch<'0' || ch>'9')    {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')    s=s*10+ch-'0',ch=getchar();return f*s;
}
struct edge{int to,lt;}e[N<<1];
int in[N],cnt,poi,idfn[N];
void add(int x,int y)
{e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;e[++cnt].to=x; e[cnt].lt=in[y]; in[y]=cnt;
}
struct node{int son[2],fa,val,sum,mn,sz;}t[N];
// val sg_odd sum sg_full mn min_dep sz
int dep[N],a[N],x,rt;
void pushup(int x)
{t[x].sz=t[ls(x)].sz+t[rs(x)].sz+1;t[x].sum=t[ls(x)].sum^t[rs(x)].sum^a[x];t[x].val=t[ls(x)].val^t[rs(x)].val^(dep[x]&1?a[x]:0);t[x].mn=min(dep[x],min(t[ls(x)].mn,t[rs(x)].mn));
}
void rotate(int x)
{int f=t[x].fa,gf=t[f].fa;int p=(rs(f)==x),k=p^1;t[gf].son[rs(gf)==f]=x;if(t[x].son[k])    t[t[x].son[k]].fa=f;t[f].son[p]=t[x].son[k]; t[x].fa=gf;t[x].son[k]=f; t[f].fa=x;pushup(f); pushup(x);
}
void splay(int x,int goal)
{while(t[x].fa!=goal){int f=t[x].fa,gf=t[f].fa;if(gf!=goal)(rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f);rotate(x);}if(!goal)    rt=x;
}
void dfs(int x,int f)
{if(f)    dep[x]=dep[f]+1;if(rt)    t[x].fa=rt,t[rt].son[1]=x;splay(x,0);for(int i=in[x];i;i=e[i].lt)    if(e[i].to!=f)dfs(e[i].to,x);
}
void insert(int x,int f,int v)
{splay(f,0); dep[x]=dep[f]+1; a[x]=v;t[t[f].son[1]].fa=x; t[x].son[1]=t[f].son[1];t[f].son[1]=x; t[x].fa=f; pushup(x); pushup(f);
}
int get(int x,int d)
{if(t[ls(x)].mn<=d)    return get(ls(x),d);else if(dep[x]<=d)    return x;else    return get(rs(x),d);
}
void put(int x)
{if(ls(x))    put(ls(x));printf("%d %d %d %d %d %dn",x,ls(x),rs(x),t[x].fa,t[x].val,t[x].mn);if(rs(x))    put(rs(x));
}
int main()
{int n=read(),l=read(),x,y,v; dep[0]=t[0].mn=inf;for(int i=1;i<=n;i++)    a[i]=read()%(l+1);for(int i=1;i<n;i++)    x=read(),y=read(),add(x,y);dep[1]=1; dfs(1,0); t[Null].fa=rt; t[rt].son[1]=Null; splay(Null,0);int q=read(),mz=0;while(q--){int opt=read();if(opt==1){x=read()^mz; splay(x,0); int remx=x;//printf("%d %dn",rs(x),remx);splay(get(rs(x),dep[x]),x); x=ls(rs(x));int ans=(dep[remx]&1)?t[x].sum^t[x].val:t[x].val;if(ans)    printf("MeiZn"),mz++;else    printf("GTYn");}else if(opt==2){x=read()^mz; v=read()^mz;// printf("%d %dn",x,v);splay(x,0); a[x]=v%(l+1); pushup(x);//put(x);
        }else{x=read()^mz; y=read()^mz; v=read()^mz;insert(y,x,v%(l+1));}}return 0;
}

转载于:.html