【bzoj2819】Nim

2014年12月9日3,7598

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

题解

从kuribohG的博客摘录的

树链查询可以变成对某些点到根的查询的叠加,这样就只需要解决查询从根发出的树链即可。如果我们询问的是从根到X节点树链上的值,那么只有X节点或X节点的祖先可能影响到X节点的答案。也就是说,一个点修改以后,只会影响它为根的子树内的节点。这样我们把这个节点所在的子树区间[l,r]修改一下即可。查询的时候,如果查询的是X点,那么返回X节点所在DFS序中的那个位置的数即可。这样我们可以用线段树区间修改,单点查询来解决这个问题。当然也可以用BIT解决。解决方法是:修改X节点的时候,把l那个点在序列中的权值修改,把r+1那个点在序列中的权值修改。查询的时候返回1~l序列中的节点权值之和。

然后在bzoj下其实是不容易爆栈的

 

  • Chenyao2014年12月15日 下午8:02 回复

    orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

    #1  
  • shijieyywd2015年4月23日 上午10:04 回复

    请问这题用lct会有什么问题吗?

    #2  
    • hzwer2015年4月23日 下午12:45 回复
      admin

      不会吧

      #21
      • shijieyywd2015年4月23日 下午2:38 回复

        反正我交上去超时了。。。

        #22
        • 魔法炮2015年4月25日 上午8:38 回复

          差分都是卡线过的 LCT必然爆炸

          #23
  • ACfastly2015年5月6日 下午8:55 回复

    快省选了orzorzorzorzorzorzorzorzorzorzorzorz

    #3  
  • 繁星2016年5月18日 下午3:11 回复

    快速读入卖萌QAQ

    #4  
  • 1112016年5月18日 下午4:53 回复

    ds

    #5