BZOJ 2819: Nim( nim + DFS序 + 树状数组 + LCA )

时间:2022-03-24 08:33:22

BZOJ 2819: Nim( nim + DFS序 + 树状数组 + LCA )

虽然vfleaking好像想卡DFS...但我还是用DFS过了...

路径上的石堆异或和=0就是必败, 否则就是必胜(nim游戏).

这样就变成一个经典问题了, 用DFS序+BIT+LCA就可以在O((N+Q)logN)时间内AC

---------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
 
using namespace std;
 
#define lowbit(x) ((x) & -(x))
 
const int maxn = 500009;
 
inline int read() {
char c = getchar();
int ret = 0;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
 
struct edge {
int to;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
 
inline void AddEdge(int u, int v) {
pt->to = v;
pt->next = head[u];
head[u] = pt++;
}
 
int N, w[maxn], seq[maxn], n, L[maxn], R[maxn];
int fa[maxn], son[maxn], top[maxn], sz[maxn], dep[maxn], Top;
 
void DFS0(int x) {
sz[x] = 1;
son[x] = -1;
for(edge* e = head[x]; e; e = e->next) if(e->to != fa[x]) {
fa[e->to] = x;
dep[e->to] = dep[x] + 1;
DFS0(e->to);
sz[x] += sz[e->to];
if(son[x] == -1 || sz[e->to] > sz[son[x]])
son[x] = e->to;
}
}
 
void DFS1(int x) {
top[x] = Top;
if(son[x] != -1)
DFS1(son[x]);
for(edge* e = head[x]; e; e = e->next)
if(e->to != fa[x] && e->to != son[x]) DFS1(Top = e->to);
}
 
int Lca(int x, int y) {
for(; top[x] != top[y]; x = fa[top[x]])
if(dep[top[x]] < dep[top[y]]) swap(x, y);
return dep[x] < dep[y] ? x : y;
}
 
void DFS2(int x) {
seq[L[x] = ++n] = x;
for(edge* e = head[x]; e; e = e->next)
if(e->to != fa[x]) DFS2(e->to);
R[x] = n;
}
 
struct BIT {
int b[maxn];
BIT() {
memset(b, 0, sizeof b);
}
inline void Modify(int x, int v) {
for(; x <= N; x += lowbit(x))
b[x] ^= v;
}
inline int Sum(int x) {
int ret = 0;
for(; x; x -= lowbit(x))
ret ^= b[x];
return ret;
}
inline int Query(int l, int r) {
return Sum(r) ^ Sum(l - 1);
}
} Bit;
 
void Init() {
N = read();
for(int i = 0; i < N; i++)
w[i] = read();
for(int i = 1; i < N; i++) {
int u = read() - 1, v = read() - 1;
AddEdge(u, v);
AddEdge(v, u);
}
}
 
void Work() {
dep[0] = 0;
fa[0] = -1;
DFS0(0);
DFS1(Top = 0);
DFS2(n = 0);
for(int i = 0; i < N; i++) {
Bit.Modify(L[i], w[i]);
Bit.Modify(R[i] + 1, w[i]);
}
int Q = read();
char c;
while(Q--) {
scanf(" %c", &c);
if(c == 'Q') {
int x = read() - 1, y = read() - 1;
int res = Bit.Query(1, L[x]) ^ Bit.Query(1, L[y]);
puts(res != w[Lca(x, y)] ? "Yes" : "No");
} else {
int p = read() - 1;
Bit.Modify(L[p], w[p]);
Bit.Modify(R[p] + 1, w[p]);
Bit.Modify(L[p], w[p] = read());
Bit.Modify(R[p] + 1, w[p]);
}
}
}
 
int main() {
Init();
Work();
return 0;
}

---------------------------------------------------------------------------------

2819: Nim

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1551  Solved: 578
[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

Yes
No
Yes
Yes
Yes

HINT

Source