← 返回题目列表

Codeforces · 1679/C

C. 鲁克斯后卫

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

你有一个大小为 $$$n \times n$$$ 的方形棋盘。行从上到下编号,编号从 $$$1$$$ 到 $$$n$$$,列从左到右编号,编号从 $$$1$$$ 到 $$$n$$$。因此,每个单元格都用一对整数 $$$(x, y)$$$ ($$$1 \le x, y \le n$$$) 表示,其中 $$$x$$$ 是行号,$$$y$$$ 是列号。

您必须执行三种类型的 $$$q$$$ 查询:

- 在单元格 $$$(x, y)$$$ 中放置一个新车。
- 从单元格 $$$(x, y)$$$ 中删除一只车。可以保证这辆车以前被关进过这个牢房。
- 检查棋盘的子矩形 $$$(x_1, y_1) - (x_2, y_2)$$$ 的每个单元格是否至少被一只车攻击。

子矩形是一组单元格 $$$(x, y)$$$,每个单元格满足两个条件:$$$x_1 \le x \le x_2$$$ 和 $$$y_1 \le y \le y_2$$$。

回想一下,如果 $$$a = c$$$ 或 $$$b = d$$$,则单元格 $$$(a, b)$$$ 会被放置在单元格 $$$(c, d)$$$ 中的车攻击。特别是,包含车的单元格会受到该车的攻击。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$)——分别是棋盘的大小和查询的数量。

以下 $$$q$$$ 行中的每一行都包含查询的描述。描述以整数 $$$t$$$ ($$$t \in \{1, 2, 3\}$$$) 开头,表示查询的类型:

- 如果 $$$t = 1$$$,则后面跟着两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) — 应该放置新车的单元格的坐标。保证在给定查询时单元格 $$$(x, y)$$$ 中没有车。
- 如果 $$$t = 2$$$,则后面跟着两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) — 要从中移除车的单元格的坐标。保证在给定查询时单元格 $$$(x, y)$$$ 中有一个车。
- 如果 $$$t = 3$$$,则遵循四个整数 $$$x_1、y_1、x_2$$$ 和 $$$y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le n$$$) — 检查每个单元格是否受到攻击的子矩形至少一只车。

保证$$$q$$$查询中至少有一个第三种类型的查询。

输出

在单独的行中打印第三种类型的每个查询的答案。如果子矩形的每个单元格都受到至少一个车的攻击,则打印“是”(不带引号)。

否则打印“No”(不带引号)。

示例

输入 #1

8 10
1 2 4
3 6 2 7 2
1 3 2
3 6 2 7 2
1 4 3
3 2 6 4 8
2 4 3
3 2 6 4 8
1 4 8
3 2 6 4 8

输出 #1

No
Yes
Yes
No
Yes

注意

考虑示例。在前两个查询之后,棋盘将如下图所示(字母 $$$R$$$ 表示车所在的单元格,第三种类型的查询的子矩形以绿色突出显示):

执行第三次和第四次查询后的棋盘:

执行第五次和第六次查询后的棋盘:

执行第七次和第八次查询后的棋盘:

执行最后两个查询后的棋盘: