#P9478. [NOI2023] 方格染色

[NOI2023] 方格染色

题目描述

有一个 nnmm 行的棋盘,共 n×mn \times m 个方格,我们约定行、列均从 11 开始标号,且第 ii 列、第 jj 行的方格坐标记为 (i,j)(i, j)。初始时,所有方格的颜色均为白色。现在,你要对这个棋盘进行 qq 次染色操作。

染色操作分为三种,分别为:

  1. 将一条横线染为黑色。具体地说,给定两个方格 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2),保证 x1x2x_1 \le x_2y1=y2y_1 = y_2,将这两个方格之间的所有方格(包括这两个方格)染为黑色。
  2. 将一条竖线染为黑色。具体地说,给定两个方格 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2),保证 x1=x2x_1 = x_2y1y2y_1 \le y_2,将这两个方格之间的所有方格(包括这两个方格)染为黑色。
  3. 将一条斜线染为黑色。具体地说,给定两个方格 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2),保证 x1x2x_1 \le x_2x2x1=y2y1x_2 - x_1 = y_2 - y_1,将这两个方格之间斜线上所有形如 (x1+i,y1+i)(x_1 + i, y_1 + i)0ix2x10 \le i \le x_2 - x_1)的方格染为黑色。这种染色操作发生的次数不超过 55 次。

现在你想知道,在经过 qq 次染色后,棋盘上有多少个黑色的方格。

输入格式

输入的第一行包含一个整数 cc,表示测试点编号。c=0c = 0 表示该测试点为样例。

输入的第二行包含三个正整数 n,m,qn, m, q,分别表示棋盘的列、行和染色操作的次数。

接下来 qq 行,每行输入五个正整数 t,x1,y1,x2,y2t, x_1, y_1, x_2, y_2,其中 t=1t = 1 表示第一种染色操作,t=2t = 2 表示第二种染色操作,t=3t = 3 表示第三种染色操作。x1,y1,x2,y2x_1, y_1, x_2, y_2 表示染色操作的四个参数。

输出格式

输出一行包含一个整数,表示棋盘上被染为黑色的方格的数量。

0
5 5 3
1 1 3 5 3
2 3 1 3 5
3 1 1 5 5

13

见附件中的 color/color2.in。
见附件中的 color/color2.ans。
见附件中的 color/color3.in。
见附件中的 color/color3.ans。
见附件中的 color/color4.in。
见附件中的 color/color4.ans。
见附件中的 color/color5.in。
见附件中的 color/color5.ans。
见附件中的 color/color6.in。
见附件中的 color/color6.ans。
见附件中的 color/color7.in。
见附件中的 color/color7.ans。

提示

【样例解释 #1】

在这组样例中,我们一共做了三次染色操作,如下图所示。

第一次操作时,将 (1,3),(2,3),(3,3),(4,3),(5,3)(1, 3), (2, 3), (3, 3), (4, 3), (5, 3) 染为黑色。

第二次操作时,将 (3,1),(3,2),(3,3),(3,4),(3,5)(3, 1), (3, 2), (3, 3), (3, 4), (3, 5) 染为黑色。

第三次操作时,将 (1,1),(2,2),(3,3),(4,4),(5,5)(1, 1), (2, 2), (3, 3), (4, 4), (5, 5) 染为黑色。

【样例解释 #2】

这个样例满足测试点 151 \sim 5 的条件限制。

【样例解释 #3】

这个样例满足测试点 696 \sim 9 的条件限制。

【样例解释 #4】

这个样例满足测试点 101310 \sim 13 的条件限制。

【样例解释 #5】

这个样例满足测试点 141714 \sim 17 的条件限制。

【样例解释 #6】

这个样例满足测试点 181918 \sim 19 的条件限制。

【样例解释 #7】

这个样例满足测试点 2020 的条件限制。

【数据范围】

对于所有测试数据保证:1n,m1091 \le n, m \le 10 ^ 91q1051 \le q \le 10 ^ 51x1,x2n1 \le x_1, x_2 \le n1y1,y2m1 \le y_1, y_2 \le m且最多有 55 次第三种染色操作

测试点编号 n,mn, m \le qq \le 特殊性质
151 \sim 5 300300
696 \sim 9 10510 ^ 5 2,0002,000
101310 \sim 13 10510 ^ 5 A
141714 \sim 17 B
181918 \sim 19
2020 10910 ^ 9

特殊性质 A:保证只有第一种染色操作。

特殊性质 B:保证只有第一种和第二种染色操作。

Update on 2023-08-04: 更新一组 Hack 数据,该 Hack 数据的 c=0c = 0