bzoj3729 Gty的游戏

本文主要是介绍bzoj3729 Gty的游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj3729
题目大意：
给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问
将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。
gty很快计算出了策略。
但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。
gty不忍心打击妹子，所以他将这个问题交给了你。
另外由于gty十分绅士，所以他将先手让给了妹子。
有三种操作类型
若为1，后跟一个数字v，表示询问在v的子树中做游戏先手是否必胜。
若为2，后跟两个数字x，y表示将节点x的石子数修改为y。
若为3，后跟三个数字u,v,x，表示为u节点添加一个儿子v，初始石子数为x。

题解：
博弈+splay
移石头这个就是经典的巴什博奕。每次移不超过L，对于每个节点的sg值就等于石子数mod(L+1).
要移到父亲节点什么的就是阶梯模型。若把子树根节点看作第0层的话，只有奇数层是“存在”的，因为若你把一些石子从偶数层移到奇数层，那么对方把它从奇数层移回去是等同的，因为最终会到0，即消失了，所以只考虑奇数层的移动偶数的不用管。即只考虑与子树根节点所处层数奇偶性不同的结点。
有加点修改操作什么的，用splay
维护四个值——子树中奇数层点的异或和，偶数层点的异或和，该点的石子数，所处层的奇偶性(都指的是原树中的信息，且奇偶性是对于整一棵树来说的)
把一个点拆成两个点分别表起始和结尾，然后以拆点后的中序遍历为关键值插入splay。比如在splay里转成1-1’，于是1的子树的所有信息就在splay中1’的左孩子那里了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 400010map<int,int > id;
struct edge
{int y,next;
}a[maxn*2];int len,first[maxn];
void ins(int x,int y)
{len++;a[len].y=y;a[len].next=first[x];first[x]=len;
}
struct node
{int fa,son[2],a1,a2,x;bool dep;
}tr[maxn*2];int tot;
int nl[maxn],nr[maxn],w[maxn];
void updata(int x)
{int lc=tr[x].son[0],rc=tr[x].son[1];tr[x].a1=tr[lc].a1^tr[rc].a1;tr[x].a2=tr[lc].a2^tr[rc].a2;if (tr[x].dep) tr[x].a1^=tr[x].x;else tr[x].a2^=tr[x].x;
}
void rotate(int x)
{int y=tr[x].fa,z=tr[y].fa;int w=(tr[y].son[0]==x)?1:0;tr[y].son[1-w]=tr[x].son[w];if (tr[x].son[w]) tr[tr[x].son[w]].fa=y;if (z){if (tr[z].son[0]==y) tr[z].son[0]=x;if (tr[z].son[1]==y) tr[z].son[1]=x;}tr[x].fa=z;tr[x].son[w]=y;tr[y].fa=x;updata(y);updata(x);
}
void splay(int x,int fa)
{while (tr[x].fa!=fa){int y=tr[x].fa,z=tr[y].fa;if (z==fa) rotate(x);else{if ((tr[z].son[0]==y)==(tr[y].son[0]==x))rotate(y),rotate(x);else rotate(x),rotate(x);}}
}
void insert(int x,int fa)
{splay(fa,0);int r=tr[fa].son[1];while (tr[r].son[0]) r=tr[r].son[0];splay(r,fa);tr[r].son[0]=x;tr[x].fa=r;updata(r);updata(fa);
}
void lk(int x)
{tr[nl[x]].son[1]=nr[x];tr[nl[x]].x=w[x];tr[nr[x]].fa=nl[x];updata(nr[x]);updata(nl[x]);
}
void dfs(int x,int fa)
{for (int k=first[x];k!=-1;k=a[k].next){int y=a[k].y;if (y==fa) continue;tr[y].dep=!tr[x].dep;lk(y);insert(y,x);dfs(y,x);}
}int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n,m,mod,i,x,y,z,op,la;scanf("%d%d",&n,&mod);mod++;len=0;memset(first,-1,sizeof(first));for (i=1;i<=n;i++) {scanf("%d",&w[i]);w[i]%=mod;nl[i]=i;nr[i]=i+n;id[i]=i;}for (i=1;i<n;i++){scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}tot=2*n;tr[0].dep=0;lk(1);tr[1].dep=1;dfs(1,0);scanf("%d",&m);la=0;while (m--){scanf("%d",&op);if (op==1){scanf("%d",&x);x^=la;x=id[x];splay(nl[x],0);splay(nr[x],nl[x]);int ans=0;if (!tr[x].dep) ans=tr[tr[nr[x]].son[0]].a1;else ans=tr[tr[nr[x]].son[0]].a2;if (ans==0) printf("GTY\n");else {printf("MeiZ\n");la++;}}else if (op==2){scanf("%d%d",&x,&y);x^=la;y^=la;x=id[x];y%=mod;splay(nl[x],0);if (tr[nl[x]].dep) tr[nl[x]].a1^=y^tr[nl[x]].x;else tr[nl[x]].a2^=y^tr[nl[x]].x;tr[nl[x]].x=y;}else{scanf("%d%d%d",&x,&y,&z);x^=la;y^=la;z^=la;z%=mod;x=id[x];id[y]=y=++n;nl[y]=++tot;nr[y]=++tot;tr[nl[y]].dep=!tr[nl[x]].dep;tr[nl[y]].x=z;tr[nr[y]].x=0;tr[nl[y]].fa=nl[x];tr[nr[y]].fa=nl[y];updata(nl[y]);updata(nr[y]);insert(nl[y],nl[x]);}}return 0;
}

这篇关于bzoj3729 Gty的游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---