CF1556G Gates to Another World

如前所述，William 非常喜欢玩电子游戏。在他最喜欢的游戏之一中，玩家角色处于一个宇宙中，每个星球都用一个从 $0$ 到 $2^n - 1$ 的二进制数编号。在每个星球上，都有传送门允许玩家从星球 $i$ 移动到星球 $j$，当且仅当 $i$ 和 $j$ 的二进制表示恰好有一位不同。 William 想考考你，看你能否处理这个游戏宇宙中的以下查询： - 毁灭编号从 $l$ 到 $r$（包含 $l$ 和 $r$）的星球。这些星球将无法再被到达。 - 判断是否可以通过若干次星球传送门，从星球 $a$ 到达星球 $b$。保证 $a$ 和 $b$ 没有被毁灭。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 50$，$1 \leq m \leq 5 \times 10^4$），分别表示每个星球编号的二进制位数和查询的数量。 接下来的 $m$ 行，每行包含一条查询，格式如下： block l r —— 表示毁灭编号从 $l$ 到 $r$ 的星球（$0 \leq l \leq r < 2^n$）。保证每个星球不会被毁灭两次。 ask a b —— 表示询问是否可以从星球 $a$ 到达星球 $b$（$0 \leq a, b < 2^n$）。保证 $a$ 和 $b$ 没有被毁灭。

对于每个 ask 查询，如果可以从星球 $a$ 到达星球 $b$，输出一行 "1"；否则输出一行 "0"（不带引号）。

第一个样例可以如下图所示：  对于查询 ask 0 7，答案为正（可以到达）。 在执行 block 3 6 查询后，图变为如下所示（被毁灭的顶点已高亮）：  此时对于查询 ask 0 7，答案为负（无法到达），因为从顶点 $0$ 到顶点 $7$ 的任意路径都必须经过被毁灭的顶点。 由 ChatGPT 4.1 翻译