[BZOJ 2819]NIM(dfs序维护树上xor值)

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

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2819

分析:

树上的nim游戏,关键就是要判断树上的一条链的异或值是否为0

这个题目有单点修改和一条链上的询问,很显然可以用树链剖分做,但是n<=50W,所以会TLE+爆栈

我们设f[x]表示点x到根节点这条路径上的异或和,那么很显然如果询问u,v上的异或和,那么ans=f[u]^f[v]^v[lca(u,v)]

那么接下来的问题就是对于每个单点修改,如何维护f[]

容易看出来,如果修改某个点x,那么f[]有变化的有且仅有以x为根的子树里面的点

这让我们可以想到dfs序,因为一个子树的dfs序是连续的,所以可以转化成一个线性序列上,而因为xor的性质,如果修改是把x的权值由v改为v',那么可以对这个子树对应的dfs序的这段区间先全部都xor v,相当于减去这个旧的权值,再全部xor v',相当于再加上新的权值。

那么现在的问题就变成了,对于一个数组,每次区间修改、单点询问

很典型的一个树状数组问题了。