← 返回题目列表

Codeforces · 1556/G

G. 异世界之门

中文机器翻译题面 查看原题

正如前面提到的,威廉非常喜欢玩电子游戏。在他最喜欢的游戏之一中,玩家角色身处一个宇宙中,其中每个行星都由从 $$$0$$$ 到 $$$2^n - 1$$$ 的二进制数指定。在每个星球上,如果 $$$i$$$ 和 $$$j$$$ 的二进制表示恰好有一位不同,则允许玩家从星球 $$$i$$$ 移动到星球 $$$j$$$ 。

William 想测试你,看看你如何处理这个游戏世界中的以下查询:

- 摧毁编号从 $$$l$$$ 到 $$$r$$$(含)的行星。这些行星不能再被移动到了。
- 找出是否有可能使用一定数量的行星门从 $$$a$$$ 行星到达 $$$b$$$ 行星。保证行星 $$$a$$$ 和 $$$b$$$ 不会被摧毁。

输入

第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$1 \leq m \leq 5 \cdot 10^4$$$),分别是每个行星名称的二进制表示的位数和查询的数量。

接下来的 $$$m$$$ 行包含两种类型的查询:

block l r — 查询编号从 $$$l$$$ 到 $$$r$$$ 的行星毁灭情况($$$0 \le l \le r < 2^n$$$)。保证没有一个星球会被毁灭两次。

询问 a b — 查询行星 $$$a$$$ 和 $$$b$$$ 之间的可达性 ($$$0 \le a, b < 2^n$$$)。可以保证行星 $$$a$$$ 和 $$$b$$$ 尚未被摧毁。

输出

对于询问类型的每个查询,如果可以从行星 $$$a$$$ 到达行星 $$$b$$$,则必须在新行中输出“1”,否则输出“0”(不带引号)。

示例

输入 #1

3 3
ask 0 7
block 3 6
ask 0 7

输出 #1

1
0

输入 #2

6 10
block 12 26
ask 44 63
block 32 46
ask 1 54
block 27 30
ask 10 31
ask 11 31
ask 49 31
block 31 31
ask 2 51

输出 #2

1
1
0
0
1
0

注意

第一个示例测试可以通过以下方式可视化:

对查询询问 0 7 的响应是肯定的。

接下来,在查询块 3 6 之后,图形将如下所示(被破坏的顶点突出显示):

对查询 Ask 0 7 的响应是否定的,因为从顶点 $$$0$$$ 到顶点 $$$7$$$ 的任何路径都必须经过被破坏的顶点之一。