【bzoj3729】Gty的游戏

2015年7月5日3,09912

Description

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

Input

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

Output

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

Sample Input

2 1000
0 0
1 2
1
1 1

Sample Output

GTY

题解

QAQ题意搞半天理解错了,1为根节点,每次选一个结点将该节点上不超过m的石子上移

每次最多取m个,只要把每个结点石子数mod(m+1),这很显然

还要知道一个阶梯博弈,类似于poj1704

考虑偶数层的结点,如果对手把某个结点的石子上移,你也可以再把它们上移,所以偶数层结点无视就好

奇数层就看成都在第一层,那么就是把奇数层的石子个数全部xor起来

插入新结点,查询子树信息,修改结点信息

强制在线的话,这几个操作只要用splay维护一下dfs序即可

编号用个map映射一下

 

  • 习近平2016年4月4日 下午3:16 回复

    %%%%可以用treap维护么

    #1  
    • 李克强2016年4月6日 上午8:53 回复

      应该可以吧

      #11
      • 江泽民2016年4月6日 下午3:03 回复

        不要因为Splay常数大就把它批判一番。西方这么多数据结构,哪个平衡树我没用过?

        #12
        • 温家宝2016年4月6日 下午7:25 回复

          你嫌常数大,你就可以写非旋转式treap啊!!!

          #13
          • CreationAugust2016年4月21日 下午1:55

            现在的年轻人啊 没说几句就膜起蛤来 naive!

            #14
          • 温家宝2016年4月23日 下午6:54

            %CA娘

            #14
          • Flandre·Scarlet2016年4月21日 下午7:53

            现在的年轻人啊 没说几句就膜起蛤来 naive!

            #14
        • sxb_2012016年4月6日 下午8:06 回复

          现在的年轻人啊 没说几句就膜起蛤来 naive!

          #13
          • wsfqk2016年4月6日 下午8:19

            捉到 Menci 一只,Orzzzz ……

            #14
  • 江泽Ming2016年4月6日 下午3:24 回复

    格奥尔吉·阿杰尔松-韦利斯基的AVL,比你们不知道高明到哪里去了,我跟它谈笑风生!

    #2  
  • 胡锦涛2016年4月6日 下午11:04 回复

    (⊙v⊙)嗯

    #3  
  • Okami2017年3月31日 下午5:09 回复

    看到楼上我全都报警啦!!!

    #4