配点: 4 点
問題文
H 行 W 列的格子,从上到下 i (1 \leq i \leq H) 第几行,从左边开始 j (1 \leq j \leq W) 选择列中的方块。 当表示为 (i, j) 。
最初所有的格子都是白色的。在这里,Q 个查询以以下形式给出。
i (1 \leq i \leq Q) 个查询:
-
t_i = 1 什么时候
- 整数 r_i, c_i 。 表示
- 白色方格 (r_i, c_i) 被涂成红色。 当满足
-
t_i = 2 什么时候
- 整数 {ra}_i, {ca}_i, {rb}_i, {cb}_i 。 表示
- 下一步 2 个条件时
Yes,否则 输出为No。 对于第- 质量 从 ({ra}_i, {ca}_i) 和正方形 看看 ({rb}_i, {cb}_i) 被涂成红色。
- 质量 从 ({ra}_i, {ca}_i) 到 ({rb}_i, {cb}_i) 通过在红色格子上上下左右移动可以到达。
超过 Q 查询。
制約
- 1 \leq H, W \leq 2000
- 1 \leq Q \leq 100000
- 1 \leq t_i \leq 2
- t_i = 1 时,1 \leq r_i \leq H、1 \leq c_i \leq W
- t_i = 2 时,1 \leq {ra}_i, {rb}_i \leq H、1 \leq {ca}_i, {cb}_i \leq W
- t_i = 1 和 t_j = 1 (1 \leq i < j \leq Q) 时,(r_i, c_i) \neq (r_j, c_j)
- 给出的所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
H W Q q_1 \vdots q_Q
在这里,q_i 是 您也可以写 i 是第几个查询的信息,以下 2 种格式中的任意一种。
1 r_i c_i
2 {ra}_i {ca}_i {rb}_i {cb}_i
出力
给定的 Q 个查询中 t_i = 2 的查询处理结果按顺序,用换行分隔。 1 请按行输出。
入力例 1
3 3 10 1 2 2 1 1 1 2 1 1 2 2 1 3 2 2 1 1 2 2 2 2 2 3 2 1 2 3 1 2 1 2 1 1 2 2 2 1 1 3 3
出力例 1
No No Yes Yes No
给定的 10 个查询按顺序处理的结果如下。
- 质量 从 (2, 2) 被涂成红色。 当满足
- 质量 从 (1, 1) 被涂成红色。 当满足
- 质量
从 (1, 1) 到 (2, 2) 无法通过在红色格子上上下左右移动到达,因为
No。 我锻炼 - 质量 从 (3, 2) 被涂成红色。 当满足
- 质量
从 (1, 1) 到 (2, 2) 无法通过在红色格子上上下左右移动到达,因为
No。 我锻炼 - 质量
从 (2, 2) 到 (3, 2) 之前是红色涂装,并且因为是在上下方向相邻的格子,所以
Yes。 我锻炼 - 质量 从 (2, 3) 被涂成红色。 当满足
- 质量 从 (2, 1) 被涂成红色。 当满足
- 质量
从 (1, 1) 到 (2, 2) 之前是格子 (1, 1) → 格子 (2, 1) → 格子 (2, 2) 可以在红色格子上上下左右移动到达,因此
Yes。 我锻炼 - 质量
从 (1, 1) 到 (3, 3) 无法通过在红色格子上上下左右移动到达,因此
No。 我锻炼
入力例 2
1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1
出力例 2
No Yes
1 请注意格子也未被涂成红色的情况。
入力例 3
5 5 42 2 3 4 3 4 2 3 2 3 2 1 4 1 2 4 1 2 2 1 1 2 1 4 5 1 3 3 2 4 2 1 3 1 3 5 2 2 4 2 3 2 2 4 2 5 2 3 4 5 1 2 3 1 2 2 2 3 1 1 2 2 2 4 5 2 2 3 2 5 3 1 4 3 2 3 3 3 5 2 3 1 3 2 1 1 5 2 4 4 5 3 1 1 4 2 1 3 2 5 2 4 3 1 4 2 2 3 3 3 1 2 1 1 2 5 2 1 4 5 3 2 4 4 2 5 2 4 2 2 4 1 2 2 2 4 1 5 2 1 2 4 2 3 1 4 1 1 4 4 2 3 2 2 1 2 1 1 5 2 1 4 2 2 4 2 3 5 1 3 2 1 3 4 1 2 3
出力例 3
No No No No No No No No No No No No No No No No No No No No No No No No Yes