#1914. 刷墙
刷墙
刷墙
题目描述
标题: 刷墙 - Problem - QOJ.ac
#10349. 刷墙
The problem was used in the following contests:
题目描述
愚人节刚刚过去了,少女心不减的小松鼠却还想做一些更有意思的事情。
在小松鼠的教室里,有一堵纯白色的墙。这堵墙可以被看作N行M列的矩形网格。她计划依次进行K次刷墙操作。对于第i次操作,她都选择了连续的若干整行或者连续的若干整列,并把它们刷成颜色ci(每种颜色可以表示为一个不同的非负整数,其中0表示白色)。
刷完之后的墙可能就是这个样子的!(对应着样例3)
在同一个格子上,后刷的颜色会完全覆盖掉之前的颜色。
请你帮助小松鼠满足她的好奇心,告诉她完成全部刷墙操作之后,有多少对相邻的格子颜色相同。
输入格式
第一行包含四个用空格隔开的非负整数 N,M,K,q(q∈{0,1},见输出格式中的说明)。
对于接下来的K行,第i行包含四个用空格隔开的非负整数typei,li,ri,ci (typei∈{0,1},0≤ci≤K),描述了一次刷墙操作。如果typei=0,表示她选择了第li行到第ri行 (1≤li≤ri≤N);如果typei=1,表示她选择了第li列到第ri列 (1≤li≤ri≤M)。
输出格式
一行一个整数。
如果q=0,输出有多少对边相邻的格子颜色相同(边相邻即有公共边的格子);
如果q=1,输出有多少对边相邻或角相邻的格子颜色相同(角相邻即有公共角的格子)。
样例输入与输出
样例1输入
3 4 3 1
0 2 3 2
1 3 3 0
1 2 2 1
样例1输出
8
样例1说明
见下图。每条小短线对应着一对颜色相同的相邻格子。
样例2输入
5 4 1 1
1 2 4 0
样例2输出
55
样例3输入
6 6 4 0
0 3 6 1
1 2 2 2
0 4 5 4
1 4 5 1
样例3输出
33
数据范围与约定
对于全部测试点,1≤N,M,K≤105。
以下部分描述了每个测试点的详细信息。
测试点编号 N,M≤ K≤ q= 其它约定 1 5000 5000 1 li=ri 2 5000 5000 1 无 3 5000 105 1 无 4, 5 105 105 0 li=ri 6, 7, 8 105 105 0 无 9, 10 105 5000 1 无 11, 12 105 105 1 ci=i 13, 14, 15, 16 105 105 1 ci∈{0,1} 17, 18, 19, 20 105 105 1 无
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4 3 1
0 2 3 2
1 3 3 0
1 2 2 1
8
样例 2
5 4 1 1
1 2 4 0
55