bzoj3729 Gty的游戏

bzoj3729 Gty的游戏

Gty的游戏

Time Limit: 20 Sec Memory Limit: 128 MB

Description

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

Input

第一行两个数字，n和L,n<=510^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。
在任意时刻，节点数不超过510^4。

Output

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

Sample Input

2 1000

0 0

1 2

1

1 1

Sample Output

GTY

调死我了QAQ。。。。。我都不知道我自己哪里写错了233.。。。于是mo了一下hzwer就过了。。。。


这个阶梯NIM有个结论（或者说是规律？？？）就是你每个都地方的式子数都对（L+1）取余，然后就转化成阶梯NIM了。。。


也就是说你的平衡树里面要维护区间的（总的那个大的根是第0层）奇数层xor和偶数层xor和
然后就是你的代码能力的考验。。。。
我觉得每个最开始写wa了后面调很久调对的了人都很帅！

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 911, L = 0, R = 1;
struct lpl{int data, rk, fa, typ, nim[2], son[2];
}node[maxn];
int n, ll, m, cnt, tnt, tot, root, Mz;
int ini[maxn], id1[maxn], id2[maxn], quan[maxn], deep[maxn], nam[maxn];
vector<int> point[maxn];
queue<int> q;
map<int, int> mp;namespace Splay{inline void update(int t){node[t].nim[0] = node[node[t].son[L]].nim[0] ^ node[node[t].son[R]].nim[0];node[t].nim[1] = node[node[t].son[L]].nim[1] ^ node[node[t].son[R]].nim[1];node[t].nim[node[t].typ] ^= node[t].data;}inline void rotate(int t){int fa = node[t].fa, grdfa = node[fa].fa, which = (node[fa].son[R] == t);node[t].fa = grdfa; node[grdfa].son[node[grdfa].son[R] == fa] = t;node[node[t].son[which ^ 1]].fa = fa; node[fa].son[which] = node[t].son[which ^ 1];node[t].son[which ^ 1] = fa; node[fa].fa = t;update(fa); update(t);}inline void splay(int t, int k){while(node[t].fa != k){int fa = node[t].fa, grdfa = node[fa].fa;if(grdfa != k){if((node[fa].son[R] == t) ^ (node[grdfa].son[R] == fa)) rotate(t);else rotate(fa);}rotate(t);}if(!k) root = t;}inline void insert(int t, int k){int now = root, fa = 0;while(now){fa = now;if(node[now].rk < t) now = node[now].son[R];else now = node[now].son[L];}node[++cnt].fa = fa; node[cnt].rk = t; node[cnt].data = quan[t];node[fa].son[node[fa].rk < t] = t; node[cnt].typ = deep[k] % 2;splay(cnt, 0);}
}inline void dfs(int t, int fa){q.push(t); for(int i = point[t].size() - 1; i >= 0; --i){if(point[t][i] == fa) continue;deep[point[t][i]] = deep[t] + 1; dfs(point[t][i], t);}q.push(t);
}inline void prepare()
{int now, p = 0;while(!q.empty()){now = q.front(); q.pop(); if(!id1[now]){id1[now] = ++tot; quan[tot] = ini[now];}else{id2[now] = ++tot;} nam[tot] = now;}for(int i = 1; i <= tot; ++i) Splay::insert(i, nam[i]);
}inline void putit(){scanf("%d%d", &n, &ll); deep[1] = 1;for(int i = 1; i <= n; ++i){scanf("%d", &ini[i]); ini[i] %= (ll + 1);mp[i] = i;}for(int u, v, i = 1; i < n; ++i){scanf("%d%d", &u, &v);point[u].push_back(v); point[v].push_back(u);}    
}inline bool Query(int t){Splay::splay(id1[t], 0); Splay::splay(id2[t], root);return node[node[node[root].son[R]].son[L]].nim[node[t].typ ^ 1];
}inline void Modify(int a, int b){Splay::splay(id1[a], 0); node[root].data = b; Splay::update(root);
}inline void Add(int u, int v, int x){mp[v] = ++tnt; v = tnt; int t1 = ++cnt, t2 = ++cnt; id1[tnt] = t1, id2[tnt] = t2;Splay::splay(id1[u], 0); int now = node[root].son[R]; deep[v] = deep[u] + 1;while(node[now].son[L])  now = node[now].son[L];node[now].son[L] = t1; node[t1].son[R] = t2; node[t1].typ = node[t2].typ = deep[v] & 1;node[t1].fa = now; node[t2].fa = t1; node[t1].data = x;Splay::update(t2); Splay::update(t1); Splay::splay(t2, 0);
}inline void workk(){int opt, a, b, c; scanf("%d", &m); tnt = n;while(m--){scanf("%d", &opt);if(opt == 1){scanf("%d", &a); a ^= Mz; a = mp[a]; ;if(Query(a)){printf("MeiZn"); Mz++;}else printf("GTYn");}if(opt == 2){scanf("%d%d", &a, &b); a ^= Mz; b ^= Mz; b %= (ll + 1);a = mp[a]; Modify(a, b);}if(opt == 3){scanf("%d%d%d", &a, &b, &c); a ^= Mz; b ^= Mz; c ^= Mz; c %= (ll + 1);a = mp[a]; Add(a, b, c);}}
}int main()
{putit();dfs(1, 0);prepare();workk();return 0;
}

转载于:.html