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 400010

map<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[],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[],rc=tr[x].son[];
    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[]==x)?:;

    tr[y].son[-w]=tr[x].son[w];
    if (tr[x].son[w]) tr[tr[x].son[w]].fa=y;

    if (z)
    {
        if (tr[z].son[]==y) tr[z].son[]=x;
        if (tr[z].son[]==y) tr[z].son[]=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[]==y)==(tr[y].son[]==x))
                rotate(y),rotate(x);
            else rotate(x),rotate(x);
        }
    }
}
void insert(int x,int fa)
{
    splay(fa,);
    int r=tr[fa].son[];
    while (tr[r].son[]) r=tr[r].son[];
    splay(r,fa);

    tr[r].son[]=x;
    tr[x].fa=r;
    updata(r);updata(fa);
}
void lk(int x)
{
    tr[nl[x]].son[]=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!=-;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=;memset(first,-,sizeof(first));
    for (i=;i<=n;i++) 
    {
        scanf("%d",&w[i]);w[i]%=mod;
        nl[i]=i;nr[i]=i+n;id[i]=i;
    }
    for (i=;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    tot=*n;tr[].dep=;
    lk();tr[].dep=;
    dfs(,);

    scanf("%d",&m);la=;
    while (m--)
    {
        scanf("%d",&op);
        if (op==)
        {
            scanf("%d",&x);x^=la;x=id[x];
            splay(nl[x],);splay(nr[x],nl[x]);
            int ans=;
            if (!tr[x].dep) ans=tr[tr[nr[x]].son[]].a1;
            else ans=tr[tr[nr[x]].son[]].a2;
            if (ans==) printf("GTY\n");
            else {printf("MeiZ\n");la++;}
        }else if (op==)
        {
            scanf("%d%d",&x,&y);x^=la;y^=la;
            x=id[x];y%=mod;
            splay(nl[x],);
            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=;
            tr[nl[y]].fa=nl[x];
            tr[nr[y]].fa=nl[y];
            updata(nl[y]);updata(nr[y]);
            insert(nl[y],nl[x]);
        }
    }
    return ;
}