← 返回题目列表

Codeforces · 1292/A

A. NEKO 的迷宫游戏

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

NEKO#ΦωΦ 刚刚在她的电脑上推出了一款新的迷宫游戏!

游戏的主要谜题是一个迷宫,其形式为 $$$2 \times n$$$ 矩形网格。 NEKO 的任务是带领一名 Nekomimi 女孩从牢房 $$$(1, 1)$$$ 到达 $$$(2, n)$$$ 的大门并逃离迷宫。女孩只能在共用一侧的牢房之间移动。

然而,在游戏过程中的某些时刻,某些单元格可能会改变其状态:从正常地面变为熔岩(这会禁止移动到该单元格中),或者反之亦然(这会使该单元格再次可以通过)。最初所有单元都是接地类型的。

经过几个小时的直播,NEKO 最终发现只有 $$$q$$$ 这样的时刻:第 $$$i$$$ 个时刻会切换单元格 $$$(r_i, c_i)$$$ 的状态(从地面到熔岩,反之亦然)。

知道了这一点,NEKO 想知道,在每个 $$$q$$$ 时刻之后,是否仍然可以从单元格 $$$(1, 1)$$$ 移动到单元格 $$$(2, n)$$$ 而无需穿过任何熔岩单元。

尽管NEKO是一位出色的主播和游戏玩家,但她仍然无法完成需要大量脑力的测验和问题。你能帮助她吗?

输入

第一行包含整数 $$$n$$$、$$$q$$$ ($$$2 \le n \le 10^5$$$、$$$1 \le q \le 10^5$$$)。

接下来的$$$q$$$行中的第$$$i$$$包含两个整数$$$r_i$$$、$$$c_i$$$ ($$$1 \le r_i \le 2$$$, $$$1 \le c_i \le n$$$),表示第$$$i$$$时刻要翻转的单元格的坐标。

保证单元格 $$$(1, 1)$$$ 和 $$$(2, n)$$$ 永远不会出现在查询列表中。

输出

对于每个时刻,如果可以从单元格 $$$(1, 1)$$$ 移动到单元格 $$$(2, n)$$$,则打印“Yes”,否则打印“No”。每次更新后都应该有准确的 $$$q$$$ 答案。

您可以以任何大小写形式打印单词(小写、大写或混合)。

示例

输入 #1

5 5
2 3
1 4
2 4
2 3
1 4

输出 #1

Yes
No
No
No
Yes

注意

我们将在这里破解示例测试:

- 经过第一次查询,女孩仍然能够达到目标。最短路径之一应该是: $$$(1,1) \to (1,2) \to (1,3) \to (1,4) \to (1,5) \to (2,5)$$$。
- 第二次查询后,不可能移动到目标,因为她能到达的最远单元格是 $$$(1, 3)$$$。
- 第四次查询后,$$$(2, 3)$$$ 没有被阻止,但现在所有第 $$$4$$$ 列都被阻止了,所以她仍然无法达到目标。
- 第五次查询后,栏杆障碍已解除,因此她可以再次前往最终目标。