AT_joi2025_yo2_a マスキングテープ (Masking Tape)

JOI 君正在用纸和遮蔽胶带玩涂色游戏。 纸是一张矩形，上面画有 $H$ 行 $W$ 列的格子。从上到下第 $i$ 行（$1 \leq i \leq H$），从左到右第 $j$ 列（$1 \leq j \leq W$）的格子称为格子 $(i, j)$。 每个格子都有一种颜色。颜色用整数表示，初始时所有格子的颜色均为 $0$。 JOI 君会用纸和遮蔽胶带进行 $Q$ 次操作。第 $k$ 次操作（$1 \leq k \leq Q$）根据整数 $q_k$ 的值按如下方式描述： - 当 $q_k = 1$ 时，此操作由整数 $x_k, y_k, c_k$ 给出。对于格子 $(x_k, y_k)$、$(x_k + 1, y_k)$、$(x_k, y_k + 1)$、$(x_k + 1, y_k + 1)$，如果该格子尚未被遮蔽胶带覆盖，则将其颜色改为 $c_k$。如果格子已被遮蔽胶带覆盖，则该格子不做任何处理。 - 当 $q_k = 2$ 时，此操作由整数 $x_k, y_k$ 给出。用遮蔽胶带覆盖格子 $(x_k, y_k)$、$(x_k + 1, y_k)$、$(x_k, y_k + 1)$、$(x_k + 1, y_k + 1)$。 所有 $Q$ 次操作结束后，揭掉所有遮蔽胶带。需要注意的是，揭掉某格子上的遮蔽胶带后，该格子的颜色会恢复为被胶带覆盖前的颜色。 给定 $Q$ 次操作的信息，请编写程序求出最终纸上所有格子的颜色。

输入按以下格式给出。 > $H$ $W$ $Q$ > （$Query\:1$） > （$Query\:2$） > $\vdots$ > （$Query\:Q$） 每个（$Query\:k$）（$1 \leq k \leq Q$）都是若干个用空格分隔的整数。第一个整数为 $q_k$，具体内容如下： - 当 $q_k = 1$ 时，该行后接 $x_k, y_k, c_k$ 共 3 个整数，用空格分隔。 - 当 $q_k = 2$ 时，该行后接 $x_k, y_k$ 共 2 个整数，用空格分隔。

请输出最终纸上所有格子的颜色，共 $H$ 行。第 $i$ 行（$1 \leq i \leq H$）输出 $W$ 个整数，中间用空格分开。第 $j$ 项（$1 \leq j \leq W$）为格子 $(i, j)$ 的颜色。

## 小子任务 1.（$32$ 分）$H = 2$，$W = 2$，且所有 $q_k = 1$（$1 \leq k \leq Q$）。 2.（$32$ 分）所有 $q_k = 1$（$1 \leq k \leq Q$）。 3.（$36$ 分）无其他额外限制。 ## 样例解释 1 我们按照顺序来看 $4$ 次操作。 第 $1$ 次操作，$q_1=1$。此时格子 $(2,2)$、$(2,3)$、$(3,2)$、$(3,3)$ 均未被遮蔽胶带覆盖，所以都被涂成颜色 $1$。 此时的纸面如下所示： ``` 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ``` 第 $2$ 次操作，$q_2=2$。将 $(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$ 这四个格子都覆盖上遮蔽胶带。 此时纸面如下，用 “*” 表示被胶带覆盖的格子： ``` 0 0* 0* 0 0 0 1* 1* 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ``` 第 $3$ 次操作，$q_3=2$。将 $(3,3)$、$(3,4)$、$(4,3)$、$(4,4)$ 这四个格子覆盖遮蔽胶带。 此时纸面如下： ``` 0 0* 0* 0 0 0 1* 1* 0 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0 ``` 第 $4$ 次操作，$q_4=1$。$(1,4)$ 和 $(2,4)$ 两个格子未被胶带覆盖，所以颜色被改为 $5$；$(1,3)$ 和 $(2,3)$ 被遮蔽胶带覆盖，没有任何变化。 此时纸面如下： ``` 0 0* 0* 5 0 0 1* 1* 5 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0 ``` 因此最终纸上所有格子的颜色如样例输出所示。 本样例满足小子任务 3 的限制。 ## 样例解释 2 本样例满足小子任务 2、3 的限制。 ## 样例解释 3 本样例满足小子任务 3 的限制。 ## 数据范围与约定 - $2 \leq H \leq 500$。 - $2 \leq W \leq 500$。 - $1 \leq Q \leq 200\,000$。 - $q_k$ 为 $1$ 或 $2$（$1 \leq k \leq Q$）。 - 当 $q_k=1$ 时，$1 \leq x_k \leq H-1$，$1 \leq y_k \leq W-1$，$1 \leq c_k \leq 10^9$。 - 当 $q_k=2$ 时，$1 \leq x_k \leq H-1$，$1 \leq y_k \leq W-1$。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译