#P9117. [春季测试 2023] 涂色游戏

[春季测试 2023] 涂色游戏

题目描述

有一天,小 D 在刷朋友圈时看到了一段游戏视频。

这个游戏的名字叫涂色游戏,视频中的游戏界面是一个 nnmm 列的网格,初始时每一个格子都是白色(用数字 00 表示)。其中每一行的左侧、每一列的上方都有一把带颜色的刷子。玩家点击某个刷子后,这个刷子会将其右侧(或下方)的一整行(或一整列)涂上同一种颜色,该行(或该列)格子原有的颜色都会被覆盖成新涂上的颜色。

下图展示的情况可以通过先将第一列涂成红色,然后将第一行涂成蓝色得到,若此时选择将第三列涂成绿色,则图中绿色方框中的格子都会变成绿色。

小 D 想用他自己编写的程序来进行视频中的游戏。在编程的过程中,小 D 在涂色逻辑的实现上却遇到了一些困难,于是他向你求助,希望你能帮他完成实现涂色逻辑部分的代码。

首先,小 D 会给你网格的行数和列数 n,mn, m,然后给出 qq 次操作,每次操作用三个整数 opti,xi,ciopt_i, x_i, c_i 表示:

  • 如果 opti=0opt_i=0,那么这次操作会将第 xix_i 涂成颜色 cic_i
  • 如果 opti=1opt_i=1,那么这次操作会将第 xix_i 涂成颜色 cic_i

在所有涂色操作结束以后,你需要输出网格中每个位置的颜色是什么。

输入格式

本题有多组测试数据。

第一行包含一个正整数 TT,表示数据组数。

接下来一共 TT 组数据,每组数据格式如下:

第一行包含三个整数 n,m,qn, m, q,分别表示涂色板的行数、列数,以及小 D 进行涂色操作的次数。

接下来 qq 行,每行包含三个整数 opti,xi,ciopt_i, x_i, c_i,表示一次操作。

输出格式

对于每组数据,输出 nn 行,每行 mm 个由单个空格隔开的整数。

其中第 ii 行第 jj 个整数表示涂色完成后网格中第 ii 行第 jj 列的方格是什么颜色。

2
5 5 9
1 5 1
0 4 0
1 4 1
0 3 0
1 3 1
0 2 0
1 2 1
0 1 0
1 1 1
3 3 3
0 1 2
0 3 1
1 1 3
1 0 0 0 0
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
1 1 1 1 1
3 2 2
3 0 0
3 1 1

提示

【样例 1 解释】

注意当一个格子没有被涂色时,其颜色为白色,用数字 00 表示。

【样例 2】

见选手目录下的 paint/paint2.in 与 paint/paint2.ans。

【数据范围】

对于所有数据,保证:

  • 1T101 \leq T \leq 101n,m1051 \leq n,m \leq 10^50q1050 \leq q \leq 10^50ci1090 \leq c_i \leq 10^9
  • opti=0opt_i=0,则 1xin1 \leq x_i \leq n;若 opti=1opt_i=1,则 1xim1 \leq x_i \leq m
  • 单个测试点中所有数据的 nmn \cdot m 的总和不超过 10610^6qq 的总和不超过 10610^6
测试点 nn \le mm \le qq \le 性质 A 性质 B
1 11 11 00
2 11
3 1010 2020
4 10510^5 ×
5
6 ×
7 1010 2020
8 5050 100100
9 ×
10 10001000 20002000 ×
11 ×
12
13 10510^5
14
15 10510^5
16
17 ×
18
19 ×
20

特殊性质 A:保证测试点中所有的 qmax(n,m)q \cdot \max(n, m) 之和不超过 10710^7

特殊性质 B:保证 opti=1opt_i = 1

【提示】

数据千万条,清空第一条。多测不清空,爆零两行泪。