BZOJ 2819: Nim
2819: Nim
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 3596 Solved: 1348
[Submit][Status][Discuss]
Description
著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,…n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：
1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。
2.把堆v中的石子数变为k。
由于vfleaking太懒了，他懒得自己动手了。请写个程序帮帮他吧。
Input
第一行一个数n，表示有多少堆石子。
接下来的一行，第i个数表示第i堆里有多少石子。
接下来n-1行，每行两个数v,u，代表v,u间有一条边直接相连。
接下来一个数q，代表操作的个数。
接下来q行，每行开始有一个字符：
如果是Q，那么后面有两个数v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略。
如果是C，那么后面有两个数v,k，代表把堆v中的石子数变为k。
对于100%的数据：
1≤N≤500000, 1≤Q≤500000, 0≤任何时候每堆石子的个数≤32767
其中有30%的数据：
石子堆组成了一条链，这3个点会导致你DFS时爆栈（也许你不用DFS？）。其它的数据DFS目测不会爆。
注意：石子数的范围是0到INT_MAX
Output
对于每个Q，输出一行Yes或No，代表对询问的回答。
Sample Input
5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3
Sample Output
No
Yes
Yes
Yes
HINT
Source
总结：
nim游戏：若每堆的石子个数异或起来不为0则有必胜策略，否则没有
所以想到可以维护两点之间的异或和
手写栈（貌似bzoj不会爆栈）
方法：
1.树剖板子
2.lca + dfs序 + 树状数组
讲一下方法2
求出dfs序
用树状数组来维护异或前缀和
及维护每个节点到根节点的异或和
然后每次查询答案为:query(x) ^ query(y) ^ a[lca(x, y)]
lca用倍增，树剖都可以
方法2比方法1少一个log
树链剖分
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
const int N = 4 * maxn;
int dfn[maxn], low[maxn], siz[maxn], xr[N], son[maxn], f[maxn], tot;
char ch[2]; int wt[maxn], dep[maxn], head[N], cnt = 1, top[maxn], a[maxn];
struct Node {
int v, nxt;
} G[N]; int q, n;
void ins(int u, int v) {
G[cnt] = (Node) {v, head[u]}; head[u] = cnt++;
}
void dfs1(int x, int fa, int deep) {
dep[x] = deep; f[x] = fa; siz[x] = 1;
int maxson = -1;
for (int i = head[x]; i; i = G[i].nxt) {
int v = G[i].v; if(v == fa) continue;
dfs1(v, x, deep + 1); siz[x] += siz[v];
if(siz[v] > maxson) maxson = siz[v], son[x] = v;
}
}
void dfs2(int x, int topf) {
dfn[x] = ++tot; wt[tot] = a[x]; top[x] = topf;
if(son[x] != 0) dfs2(son[x], topf);
for (int i = head[x]; i; i = G[i].nxt) {
int v = G[i].v; if(v == f[x] || v == son[x]) continue;
dfs2(v, v);
} low[x] = tot;
}
void update(int o) {
xr[o] = xr[o << 1] ^ xr[o << 1 | 1];
}
void build(int o, int l, int r) {
if(l == r) {
xr[o] = wt[l]; return;
} int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
update(o);
}
void modify(int o, int l, int r, int ql, int z) {
if(l == r) {
xr[o] = z; return;
} int mid = (l + r) >> 1;
if(ql <= mid) modify(o << 1, l, mid, ql, z);
else modify(o << 1 | 1, mid + 1, r, ql, z);
update(o);
}
int query(int o, int l, int r, int ql ,int qr) {
if(ql <= l && r <= qr) return xr[o];
int mid = (l + r) >> 1; int res = 0;
if(ql <= mid) res ^= query(o << 1, l, mid, ql, qr);
if(qr > mid) res ^= query(o << 1 | 1, mid + 1, r, ql, qr);
return res;
}
int Query(int x, int y) {
int res = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res ^= query(1, 1, n, dfn[top[x]], dfn[x]); x = f[top[x]];
} if(dep[x] > dep[y]) swap(x, y);
res ^= query(1, 1, n, dfn[x], dfn[y]); return (res == 0);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n - 1; ++i) {
int x, y; scanf("%d%d", &x, &y);
ins(x, y); ins(y, x);
}
dfs1(1, -1, 0); dfs2(1, 1); build(1, 1, n);
scanf("%d", &q);
while(q--) {
scanf("%s", ch);
if(ch[0] == 'Q') {
int x, y; scanf("%d%d", &x, &y);
(!Query(x, y)) ?printf("Yes\n") :printf("No\n");
}
else {
int k, x; scanf("%d%d", &k, &x); modify(1, 1, n, dfn[k], x);
}
}
return 0;
}
dfs序 + lca + 树状数组
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
const int N = 500005;
int head[maxn], cnt = 1, dfn[N], low[N], n;
int c[N], a[N], dep[N], f[N][21];
struct Node {
int v, nxt;
} G[maxn]; int tot = 0, q; char ch[5];
void ins(int u, int v) {
G[cnt] = (Node) {v, head[u]}; head[u] = cnt++;
}
void dfs(int x, int fa, int deep) {
f[x][0] = fa; dep[x] = deep; dfn[x] = ++tot;
for (int i = 1; i <= 20 && f[f[x][i - 1]][i - 1]; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = head[x]; i; i = G[i].nxt) {
int v = G[i].v; if(v == fa) continue;
dfs(v, x, deep + 1);
} low[x] = tot;
}
int lowbit(int x) {
return x & (-x);
}
void modify(int x, int y) {
for (int i = x; i <= n; i += lowbit(i)) c[i] ^= y;
}
int query(int x) {
int ret = 0;
for (int i = x; i; i -= lowbit(i)) ret ^= c[i];
return ret;
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; --i) {
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
} if(x == y) return x;
for (int i = 20; i >= 0; --i) {
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
} return f[x][0];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n - 1; ++i) {
int x, y; scanf("%d%d", &x, &y);
ins(x, y); ins(y, x);
}
dfs(1, 0, 1);
for (int i = 1; i <= n; ++i) {
modify(dfn[i], a[i]); modify(low[i] + 1, a[i]);
} scanf("%d", &q);
while(q--) {
int x, y;
scanf("%s%d%d", ch, &x, &y);
if(ch[0] == 'Q') (query(dfn[x]) ^ query(dfn[y]) ^ a[LCA(x, y)]) ?puts("Yes") :puts("No");
else {
modify(dfn[x], a[x] ^ y); modify(low[x] + 1, a[x] ^ y); a[x] = y;
}
}
return 0;
}