A6019 | $「2017 山东三轮集训 Day4」Right$

时间限制4s

内存限制512MB

通过 / 提交0/0

题目描述

JOHNKRAM和 C-SUNSHINE 在玩一个游戏。游戏规则如下：有若干堆石子，游戏前选定一个正整数 $ p $，JOHNKRAM 先手，两个人轮流操作。定义一次操作是选择某一堆石子，然后拿出其中的 $ p ^ k (k \in N) $ 个石子扔掉，不能操作者输。 C_SUNSHINE 表示判定谁能赢太简单了，于是他放了 $ n $ 堆石子，编号为 $ 1 \sim n $。他每次把编号在某个区间内的石子堆加上若干个石子，或者询问以编号在某个区间内的石子堆进行游戏，是谁胜利。JOHNKRAM 表示他不会做，于是他来向你求助。

第一行三个数 $ n, q, p $，$ n $ 表示序列的长度，$ q $ 表示接下来操作的次数，$ p $ 的意义如题目描述中所说。 接下来一行 $ n $ 个数，第 $ i $ 个数表示初始时第 $ i $ 堆石子的石子数量。 接下来 $ q $ 行每行第一个数 $ t $ 表示操作类型，$ t = 0 $ 表示修改，$ t = 1 $ 表示询问。 对于一个修改操作，该行还会有三个数 $ l, r, x $，表示把 $ [l \ldots r] $ 的所有石子堆加上 $ x $ 个石子。 对于一个询问操作，该行还会有两个数 $ l, r $，表示询问以 $ [l \ldots r] $ 的所有石子堆进行游戏是谁胜。

对于每一个询问操作，如果 JOHNKRAM 胜利则输出 $ 1 $，否则输出 $ 0 $。

输入 #1

10 9 3
2 6 2 5 8 7 4 3 4 1
1 1 10
0 5 7 15
1 1 3
0 3 9 11
1 3 7
0 4 5 53
0 1 2 26
1 6 10
1 4 9

输出 #1

C++ 编辑器

输入

输出