P9478 [NOI2023] 方格染色

题目描述

有一个 $n$ 列 $m$ 行的棋盘,共 $n \times m$ 个方格,我们约定行、列均从 $1$ 开始标号,且第 $i$ 列、第 $j$ 行的方格坐标记为 $(i, j)$。初始时,所有方格的颜色均为白色。现在,你要对这个棋盘进行 $q$ 次染色操作。 染色操作分为三种,分别为: 1. 将一条横线染为黑色。具体地说,给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$,保证 $x_1 \le x_2$,$y_1 = y_2$,将这两个方格之间的所有方格(包括这两个方格)染为黑色。 2. 将一条竖线染为黑色。具体地说,给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$,保证 $x_1 = x_2$,$y_1 \le y_2$,将这两个方格之间的所有方格(包括这两个方格)染为黑色。 3. 将一条斜线染为黑色。具体地说,给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$,保证 $x_1 \le x_2$,$x_2 - x_1 = y_2 - y_1$,将这两个方格之间斜线上所有形如 $(x_1 + i, y_1 + i)$($0 \le i \le x_2 - x_1$)的方格染为黑色。**这种染色操作发生的次数不超过 $5$ 次。** 现在你想知道,在经过 $q$ 次染色后,棋盘上有多少个黑色的方格。

输入格式

输出格式

说明/提示

**【样例解释 #1】** 在这组样例中,我们一共做了三次染色操作,如下图所示。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7ojo6cs1.png) 第一次操作时,将 $(1, 3), (2, 3), (3, 3), (4, 3), (5, 3)$ 染为黑色。 第二次操作时,将 $(3, 1), (3, 2), (3, 3), (3, 4), (3, 5)$ 染为黑色。 第三次操作时,将 $(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)$ 染为黑色。 **【样例解释 #2】** 这个样例满足测试点 $1 \sim 5$ 的条件限制。 **【样例解释 #3】** 这个样例满足测试点 $6 \sim 9$ 的条件限制。 **【样例解释 #4】** 这个样例满足测试点 $10 \sim 13$ 的条件限制。 **【样例解释 #5】** 这个样例满足测试点 $14 \sim 17$ 的条件限制。 **【样例解释 #6】** 这个样例满足测试点 $18 \sim 19$ 的条件限制。 **【样例解释 #7】** 这个样例满足测试点 $20$ 的条件限制。 **【数据范围】** 对于所有测试数据保证:$1 \le n, m \le 10 ^ 9$,$1 \le q \le 10 ^ 5$,$1 \le x_1, x_2 \le n$,$1 \le y_1, y_2 \le m$,**且最多有 $5$ 次第三种染色操作**。 |测试点编号|$n, m \le$|$q \le$|特殊性质| |:-:|:-:|:-:|:-:| |$1 \sim 5$|$300$|$300$|无| |$6 \sim 9$|$10 ^ 5$|$2,000$|无| |$10 \sim 13$|$10 ^ 5$|$10 ^ 5$|A| |$14 \sim 17$|$10 ^ 5$|$10 ^ 5$|B| |$18 \sim 19$|$10 ^ 5$|$10 ^ 5$|无| |$20$|$10 ^ 9$|$10 ^ 5$|无| 特殊性质 A:保证只有第一种染色操作。 特殊性质 B:保证只有第一种和第二种染色操作。 Update on 2023-08-04: 更新一组 Hack 数据,该 Hack 数据的 $c = 0$。