#PQJ1970x10349. QOJ 1970_10349

    ID: 2765 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2017 互测差分枚举

QOJ 1970_10349

标题: 刷墙 - Problem - QOJ.ac

#10349. 刷墙

Statistics

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 无