{"problem":{"name":"「QFOI R1」头","description":{"content":"小 R 是一个可爱的女孩子。有一天，她在被摸头时，突然灵光乍现，便随手加强了一道题给你做。 这道题的名字叫涂色游戏。初始时你有一个 $n$ 行 $m$ 列的网格，所有格子上都没有颜色。有 $k$ 种颜色的刷子，颜色编号为 $1\\sim k$。然后给出 $q$ 次操作，每次操作给出 $op,l,r,c,t$ 五个参数： - 如果 $op=1$，表示将第 $l\\sim r$ 行的所有格子涂成颜色 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9715"},"statements":[{"statement_type":"Markdown","content":"小 R 是一个可爱的女孩子。有一天，她在被摸头时，突然灵光乍现，便随手加强了一道题给你做。\n\n这道题的名字叫涂色游戏。初始时你有一个 $n$ 行 $m$ 列的网格，所有格子上都没有颜色。有 $k$ 种颜色的刷子，颜色编号为 $1\\sim k$。然后给出 $q$ 次操作，每次操作给出 $op,l,r,c,t$ 五个参数：\n\n- 如果 $op=1$，表示将第 $l\\sim r$ 行的所有格子涂成颜色 $c$。\n- 如果 $op=2$，表示将第 $l\\sim r$ 列的所有格子涂成颜色 $c$。\n- 如果 $t=0$，意味着如果涂色时遇到已经被染色的格子，就不再进行染色。\n- 如果 $t=1$，意味着如果涂色时遇到已经被染色的格子，就用新的颜色覆盖它。\n\n在所有涂色操作结束以后，对于每种颜色，求出有多少个格子被染成了这种颜色。\n\n## Input\n\n第一行四个整数 $n,m,k,q$，表示行数、列数、颜色数和操作数。\n\n接下来 $q$ 行，每行五个整数 $op,l,r,c,t$，表示这次操作的参数。\n\n## Output\n\n一行 $k$ 个整数，第 $i$ 个整数表示被染成颜色 $i$ 的格子数量。\n\n[samples]\n\n## Background\n\n可以看看这个讨论：<https://www.luogu.com.cn/discuss/703835>。\n\n## Note\n\n**样例 $1$ 解释**\n\n用浅灰色表示颜色 $1$，灰色表示颜色 $2$。\n\n涂色过程如图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/gl7dmh5b.png)\n\n共有 $17$ 个区域被染成颜色 $1$，$7$ 个区域被染成颜色 $2$。\n\n---\n\n**数据范围**\n\n本题共 $20$ 个测试点，每个测试点 $5$ 分。\n\n对于全部数据，保证 $1\\le n,m,q\\le 2\\times 10^6$，$1\\le k\\le 5\\times 10^5$，$op\\in\\{1,2\\}$，若 $op=1$ 则 $1\\le l\\le r\\le n$，若 $op=2$ 则 $1\\le l\\le r\\le m$，$1\\le c\\le k$，$t\\in\\{0,1\\}$。\n\n- 对于测试点 $1\\sim 3$：保证 $n,m,k,q\\le 200$。\n- 对于测试点 $4\\sim 6$：保证 $n,m,k,q\\le 2\\times 10^3$。\n- 对于测试点 $7\\sim 9$：保证 $n,m,k,q\\le 10^5$，$op=1$。\n- 对于测试点 $10\\sim 12$：保证 $n,m,k,q\\le 10^5$，$t=1$。\n- 对于测试点 $13\\sim 18$：保证 $n,m,k,q\\le 10^5$。\n- 对于测试点 $19\\sim 20$：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9715","tags":["线性数据结构","洛谷原创","O2优化","洛谷月赛","链表"],"sample_group":[["5 5 2 4\n1 2 4 1 0\n2 4 5 1 1\n2 2 4 2 0\n1 1 1 2 1","17 7"],["5 5 3 6\n2 1 3 3 1\n2 2 4 1 0\n1 4 4 2 0\n2 1 1 1 0\n1 2 5 2 0\n1 1 5 3 0","5 4 16"]],"created_at":"2026-03-03 11:09:25"}}