A6909. 车的防守
编程题
普及+/提高
知识点
题目描述
你有一个 $n\times n$ 的国际象棋棋盘。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。
因此每个格子用一对整数 $(x,y)$ 表示（$1\le x,y\le n$），其中 $x$ 是行号，$y$ 是列号。
你需要执行 $q$ 次操作，操作有三种类型：
1. 在格子 $(x,y)$ 上放置一个新的车。
2. 从格子 $(x,y)$ 上移除一个车。保证操作前该格子上有车。
3. 检查子矩形 $(x_1,y_1)-(x_2,y_2)$ 内的每个格子是否都被至少一个车攻击。
子矩形是指所有满足 $x_1\le x\le x_2$ 且 $y_1\le y\le y_2$ 的格子 $(x,y)$ 的集合。
回忆：如果在 $(c,d)$ 放置一个车，则格子 $(a,b)$ 会被该车攻击，当且仅当 $a=c$ 或 $b=d$。
特别地，包含车本身的格子也会被该车攻击。
对于每个第 3 类操作，如果子矩形内每个格子都被至少一个车攻击，输出
因此每个格子用一对整数 $(x,y)$ 表示（$1\le x,y\le n$），其中 $x$ 是行号，$y$ 是列号。
你需要执行 $q$ 次操作，操作有三种类型：
1. 在格子 $(x,y)$ 上放置一个新的车。
2. 从格子 $(x,y)$ 上移除一个车。保证操作前该格子上有车。
3. 检查子矩形 $(x_1,y_1)-(x_2,y_2)$ 内的每个格子是否都被至少一个车攻击。
子矩形是指所有满足 $x_1\le x\le x_2$ 且 $y_1\le y\le y_2$ 的格子 $(x,y)$ 的集合。
回忆：如果在 $(c,d)$ 放置一个车，则格子 $(a,b)$ 会被该车攻击，当且仅当 $a=c$ 或 $b=d$。
特别地，包含车本身的格子也会被该车攻击。
对于每个第 3 类操作，如果子矩形内每个格子都被至少一个车攻击，输出
Yes，否则输出 No。输入格式
第一行包含两个整数 $n$ 和 $q$。
接下来 $q$ 行，每行描述一个操作。每个操作以一个整数 $t$（$t\in\{1,2,3\}$）开头：
- 若 $t=1$：输入 $1\ x\ y$，表示在 $(x,y)$ 放置一个车。保证该格子当前没有车。
- 若 $t=2$：输入 $2\ x\ y$，表示移除 $(x,y)$ 上的车。保证该格子当前有车。
- 若 $t=3$：输入 $3\ x_1\ y_1\ x_2\ y_2$，表示询问子矩形 $(x_1,y_1)-(x_2,y_2)$。
保证在 $q$ 个操作中至少有一个为第 3 类操作。
接下来 $q$ 行，每行描述一个操作。每个操作以一个整数 $t$（$t\in\{1,2,3\}$）开头：
- 若 $t=1$：输入 $1\ x\ y$，表示在 $(x,y)$ 放置一个车。保证该格子当前没有车。
- 若 $t=2$：输入 $2\ x\ y$，表示移除 $(x,y)$ 上的车。保证该格子当前有车。
- 若 $t=3$：输入 $3\ x_1\ y_1\ x_2\ y_2$，表示询问子矩形 $(x_1,y_1)-(x_2,y_2)$。
保证在 $q$ 个操作中至少有一个为第 3 类操作。
输出格式
对每个第 3 类操作，输出一行
Yes 或 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
说明/提示
## 数据范围
- $1\le n\le 10^5$
- $1\le q\le 2\times 10^5$
## 说明/提示
请参考示例。前两次操作后，棋盘如下图所示（字母 $R$ 表示有车的格子，绿色高亮部分为第三类操作的子矩形）：
执行第三和第四次操作后的棋盘： 
执行第五和第六次操作后的棋盘： 
执行第七和第八次操作后的棋盘： 
执行最后两次操作后的棋盘：
- $1\le n\le 10^5$
- $1\le q\le 2\times 10^5$
## 说明/提示
请参考示例。前两次操作后，棋盘如下图所示（字母 $R$ 表示有车的格子，绿色高亮部分为第三类操作的子矩形）：
执行第三和第四次操作后的棋盘： 
执行第五和第六次操作后的棋盘： 
执行第七和第八次操作后的棋盘： 
执行最后两次操作后的棋盘：
