社区讨论

洛谷官方来看看这比赛的最后一题

hhmy_ddxw__awa
工单反馈版参与者 8已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lo169daf
此快照首次捕获于
2023/10/22 15:53
2 年前
此快照最后确认于
2023/11/02 15:28
2 年前
查看原帖
不用说了，这题和比赛题至少有4,5分相像！！！
比赛：# 「QFOI R1」头

题目描述

小 R 是一个可爱的女孩子。有一天，她在被摸头时，突然灵光乍现，便随手加强了一道题给你做。
这道题的名字叫涂色游戏。初始时你有一个 nn 行 mm 列的网格，所有格子上都没有颜色。有 kk 种颜色的刷子，颜色编号为 1∼k1\sim k。然后给出 qq 次操作，每次操作给出 op,l,r,c,top,l,r,c,t 五个参数：
  • 如果 op=1op=1，表示将第 l∼rl\sim r 行的所有格子涂成颜色 cc。
  • 如果 op=2op=2，表示将第 l∼rl\sim r 列的所有格子涂成颜色 cc。
  • 如果 t=0t=0，意味着如果涂色时遇到已经被染色的格子，就不再进行染色。
  • 如果 t=1t=1，意味着如果涂色时遇到已经被染色的格子，就用新的颜色覆盖它。
在所有涂色操作结束以后，对于每种颜色，求出有多少个格子被染成了这种颜色。

输入格式

第一行四个整数 n,m,k,qn,m,k,q，表示行数、列数、颜色数和操作数。
接下来 qq 行，每行五个整数 op,l,r,c,top,l,r,c,t，表示这次操作的参数。

输出格式

一行 kk 个整数，第 ii 个整数表示被染成颜色 ii 的格子数量。

样例 #1

样例输入 #1

CPP
5 5 2 4
1 2 4 1 0
2 4 5 1 1
2 2 4 2 0
1 1 1 2 1

样例输出 #1

CPP
17 7

样例 #2

样例输入 #2

CPP
5 5 3 6
2 1 3 3 1
2 2 4 1 0
1 4 4 2 0
2 1 1 1 0
1 2 5 2 0
1 1 5 3 0

样例输出 #2

CPP
5 4 16

提示

样例 11 解释
用浅灰色表示颜色 11，灰色表示颜色 22。
涂色过程如图所示：
共有 1717 个区域被染成颜色 11，77 个区域被染成颜色 22。
数据范围
本题共 2020 个测试点，每个测试点 55 分。
对于全部数据，保证 1≤n,m,q≤2×1061\le n,m,q\le 2\times 10^6，1≤k≤5×1051\le k\le 5\times 10^5，op∈{1,2}op\in\{1,2\}，若 op=1op=1 则 1≤l≤r≤n1\le l\le r\le n，若 op=2op=2 则 1≤l≤r≤m1\le l\le r\le m，1≤c≤k1\le c\le k，t∈{0,1}t\in\{0,1\}。
  • 对于测试点 1∼31\sim 3：保证 n,m,k,q≤200n,m,k,q\le 200。
  • 对于测试点 4∼64\sim 6：保证 n,m,k,q≤2×103n,m,k,q\le 2\times 10^3。
  • 对于测试点 7∼97\sim 9：保证 n,m,k,q≤105n,m,k,q\le 10^5，op=1op=1。
  • 对于测试点 10∼1210\sim 12：保证 n,m,k,q≤105n,m,k,q\le 10^5，t=1t=1。
  • 对于测试点 13∼1813\sim 18：保证 n,m,k,q≤105n,m,k,q\le 10^5。
  • 对于测试点 19∼2019\sim 20：无特殊限制。
而这时别的题（洛谷里的）

涂色

题目描述

小 C 正在用彩铅给一张 nn 行 mm 列的方格纸涂色。初始时，所有方格都是空白的。
他一共要进行 qq 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 11 层颜色。
小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 kk 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。
小 C 想知道，在最终共有多少方格被涂上了颜色。

输入格式

第一行四个整数 n,m,q,kn,m,q,k。
接下来 qq 行，每行两个整数 op,xop,x。
若 op=1op=1，则表示给第 xx 行的所有方格都添加 11 层颜色；
若 op=2op=2，则表示给第 xx 列的所有方格都添加 11 层颜色。

输出格式

一个整数，表示在最终共有多少方格被涂上了颜色。

样例 #1

样例输入 #1

CPP
3 4 5 3
1 3
2 4
1 2
1 3
2 2

样例输出 #1

CPP
8

提示

【样例解释 #1】

第 11 行第 11 列的方格没有被涂上颜色，第 11 行第 22 列的方格被涂上了 11 层颜色，第 11 行第 33 列的方格没有被涂上颜色，第 11 行第 44 列的方格被涂上了 11 层颜色；
第 22 行第 11 列的方格被涂上了 11 层颜色，第 22 行第 22 列的方格被涂上了 22 层颜色，第 22 行第 33 列的方格被涂上了 11 层颜色，第 22 行第 44 列的方格被涂上了 22 层颜色；
第 33 行第 11 列的方格被涂上了 22 层颜色，第 33 行第 22 列的方格的颜色被擦掉了，第 33 行第 33 列的方格被涂上了 22 层颜色，第 33 行第 44 列的方格的颜色也被擦掉了；
最终，共有 88 个方格被涂上了颜色。

【样例 #2】

见附加文件中的 paint/paint2.in 与 paint/paint2.ans。
该样例满足测试点 11 的限制。

【样例 #3】

见附加文件中的 paint/paint3.in 与 paint/paint3.ans。
该样例满足测试点 55 的限制。

【样例 #4】

见附加文件中的 paint/paint4.in 与 paint/paint4.ans。
该样例满足测试点 2020 的限制。

【数据范围】

对于 100%100\% 的数据，1≤n,m≤2×1051 \le n,m \le 2\times 10^5，1≤k≤q≤5×1051 \le k \le q \le 5 \times 10^5，op∈{1,2}op \in \{1,2\}，保证当 op=1op=1 时 1≤x≤n1 \le x \le n，当 op=2op=2 时 1≤x≤m1 \le x \le m。
测试点编号n,m≤n,m \leq≤q \le特殊性质
1∼41\sim43000300030003000无
5∼95\sim9300030005×1055\times10^5无
10∼1210\sim122×1052\times10^55×1055\times10^5A
13∼1613\sim162×1052\times10^55×1055\times10^5B
17∼2017\sim202×1052\times10^55×1055\times10^5无
特殊性质 A：保证 op=1op=1。
特殊性质 B：保证 k=2k=2。
真是泰裤辣！

回复

共 8 条回复，欢迎继续交流。

正在加载回复...