{"problem":{"name":"[COI 2020] Paint","description":{"content":"你一定用过画图软件的一键填充功能吧？如果拓展到像素层面中，如果一个大连通块内所有像素的颜色相同，那么将一个像素染色，那么整个连通块内的所有像素都会被染色。 现在给定一个 $R\\times S$ 的像素图，给定 $Q$ 个染色操作： - 将 $(r_i,s_i)$ 染为颜色 $c_i$。 求染色过后的整个像素图。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":512000},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8427"},"statements":[{"statement_type":"Markdown","content":"你一定用过画图软件的一键填充功能吧？如果拓展到像素层面中，如果一个大连通块内所有像素的颜色相同，那么将一个像素染色，那么整个连通块内的所有像素都会被染色。\n\n现在给定一个 $R\\times S$ 的像素图，给定 $Q$ 个染色操作：\n\n- 将 $(r_i,s_i)$ 染为颜色 $c_i$。\n\n求染色过后的整个像素图。\n\n## Input\n\n第一行两个整数 $R,S$ 代表像素图大小。          \n接下来 $R$ 行每行 $S$ 个整数，代表像素图的初始颜色。         \n第 $R+2$ 行一个整数 $Q$ 代表操作个数。         \n接下来 $Q$ 行每行三个整数 $r_i,s_i,c_i$ 代表一次染色操作。\n\n## Output\n\n$R$ 行每行 $S$ 个整数代表染色后的像素图。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n假设 $0$ 为白色，$1$ 为红色，$2$ 为蓝色，$3$ 为绿色，$4$ 为黄色，那么如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/4hvovfq7.png)\n\n#### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n- Subtask 1（8 pts）：$1 \\le R \\times S \\le 10^4$，$1 \\le Q \\le 10^4$。\n- Subtask 2（9 pts）：$R=1$，$1 \\le S \\le 2 \\times 10^5$，$1 \\le Q \\le 10^5$。\n- Subtask 3（31 pts）：$1 \\le R \\times S \\le 2 \\times 10^5$，$1 \\le Q \\le 10^5$，颜色只有 $0$ 和 $1$。\n- Subtask 4（52 pts）：$1 \\le R \\times S \\le 2 \\times 10^5$，$1 \\le Q \\le 10^5$。\n\n对于 $100\\%$ 的数据，$1 \\le r_i \\le R$，$1 \\le s_i \\le S$，$0 \\le c_i \\le 10^5$，颜色区间为 $[0,10^5]$。\n\n#### 说明\n\n翻译自 [Croatian Olympiad in Informatics 2020 A Paint](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8427","tags":["2020","COI（克罗地亚）"],"sample_group":[["12 11\n1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 0 0 0 1 1 1 1\n1 1 1 0 0 0 0 0 1 1 1\n1 1 0 0 0 0 0 0 0 1 1\n1 0 0 0 2 2 2 0 0 0 1\n1 0 0 0 2 2 2 0 0 0 1\n1 0 0 0 2 2 2 0 0 0 1\n1 0 0 0 0 0 0 0 0 0 1\n1 1 0 0 0 2 0 0 0 1 1\n0 1 1 0 0 2 0 0 1 1 0\n0 0 1 1 0 0 0 1 1 0 0\n0 0 0 1 1 1 1 1 0 0 0\n2\n5 5 3\n6 2 4","1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 4 4 4 1 1 1 1\n1 1 1 4 4 4 4 4 1 1 1\n1 1 4 4 4 4 4 4 4 1 1\n1 4 4 4 3 3 3 4 4 4 1\n1 4 4 4 3 3 3 4 4 4 1\n1 4 4 4 3 3 3 4 4 4 1\n1 4 4 4 4 4 4 4 4 4 1\n1 1 4 4 4 2 4 4 4 1 1\n0 1 1 4 4 2 4 4 1 1 0\n0 0 1 1 4 4 4 1 1 0 0\n0 0 0 1 1 1 1 1 0 0 0"],["4 4\n1 0 1 3\n1 3 2 2\n3 3 1 2\n2 2 1 3\n3\n1 2 3\n3 2 1\n4 2 3","1 1 1 3\n1 1 2 2\n1 1 1 2\n3 3 1 3"],["6 6\n1 2 1 2 2 2\n3 1 2 1 3 1\n3 3 2 3 2 2\n2 3 1 3 3 2\n3 3 3 3 3 3\n2 3 2 2 2 1\n4\n6 2 2\n3 5 2\n3 2 3\n1 2 3","1 3 1 2 2 2\n3 1 3 1 3 1\n3 3 3 3 3 3\n3 3 1 3 3 3\n3 3 3 3 3 3\n3 3 3 3 3 1"]],"created_at":"2026-03-03 11:09:25"}}