← 返回题目列表

AtCoder · typical90_l

012. 红画(★4)

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

配点: 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