题意理解

我们有一个 $n \times m$ 的巨大棋盘，需要进行 $q$ 次染色操作，操作分为三种类型：

• 横线操作：染黑整行的一段连续格子
• 竖线操作：染黑整列的一段连续格子
• 斜线操作：染黑一条45度斜线（最多5次）

最终需要计算被染黑的格子总数。

核心挑战：$n, m$ 可达 $10^9$，无法直接存储整个棋盘状态。

核心思路

关键观察 1：问题分解

由于操作之间会有重叠，直接相加会重复计算。需要使用容斥原理：

总黑色格子数 = 横线覆盖数 + 竖线覆盖数 + 斜线覆盖数

• 横线竖线交集数 - 横线斜线交集数 - 竖线斜线交集数

• 横线竖线斜线三交集数

关键观察 2：离散化处理

虽然棋盘很大 ($10^9 \times 10^9$)，但操作数 $q \leq 10^5$，且斜线操作最多5次。我们可以将所有涉及的坐标离散化：

• 横坐标离散化点：所有横线操作的 $x_1, x_2+1$，所有竖线操作的 $x$，所有斜线操作的 $x_1, x_2$
• 纵坐标离散化点：所有横线操作的 $y$，所有竖线操作的 $y_1, y_2+1$，所有斜线操作的 $y_1, y_2$

这样将平面划分为 $O(q) \times O(q)$ 个矩形块。

关键观察 3：扫描线算法

对于横线和竖线的覆盖，可以使用扫描线算法：

处理横线覆盖：

• 对每个 $y$ 坐标，维护当前行被横线覆盖的区间
• 使用线段树维护列上的覆盖情况

处理竖线覆盖：类似方法，对每个 $x$ 坐标维护覆盖区间。

算法框架

方法一：基于离散化的容斥计算

1. 坐标离散化

   • 提取所有操作的边界坐标
   • 对横纵坐标分别排序去重

2. 分别计算各类覆盖

   • 计算所有横线覆盖的格子数（考虑区间合并）
   • 计算所有竖线覆盖的格子数
   • 计算所有斜线覆盖的格子数

3. 计算交集

   • 横线与竖线交集：即横线竖线交点的格子
   • 横线与斜线交集：枚举每条斜线，计算与各横线的交点
   • 竖线与斜线交集：类似方法
   • 三交集：横线、竖线、斜线的公共交点

方法二：扫描线 + 线段树

对于只有横竖线的情况（特殊性质B）：

1. 横向扫描：

   • 按 $y$ 坐标扫描，维护当前行被横线覆盖的区间
   • 使用线段树记录每列被竖线覆盖的情况

2. 纵向扫描：

   • 按 $x$ 坐标扫描，维护当前列被竖线覆盖的区间
   • 使用线段树记录每行被横线覆盖的情况

3. 合并结果：使用容斥原理避免重复计数。

方法三：特殊性质处理

特殊性质A（只有横线）：

• 简单的区间合并问题
• 对每行分别处理，合并重叠区间

特殊性质B（只有横竖线）：

• 设横线覆盖格子数为 $A$，竖线覆盖格子数为 $B$，交集数为 $C$
• 答案 = $A + B - C$
• $C$ 可以通过求所有横线区间与竖线区间的交集得到

斜线处理技巧

由于斜线操作最多5次，可以暴力处理：

1. 单独计算每条斜线：斜线 $(x_1,y_1)$ 到 $(x_2,y_2)$ 覆盖格子数为 $(x_2-x_1+1)$

2. 斜线之间的交集：最多 $C_5^2 = 10$ 对，可以暴力判断是否相交

3. 斜线与横竖线的交集：

   • 斜线 $y = x + b$ 与横线 $y = c$ 的交点：$x = c - b$
   • 斜线 $y = x + b$ 与竖线 $x = c$ 的交点：$y = c + b$
   • 检查交点是否在各自线段范围内

复杂度分析

离散化方法

• 离散化：$O(q \log q)$
• 横竖线处理：$O(q \log q)$ 的扫描线
• 斜线处理：$O(5 \times q)$ 的暴力计算
• 总体：$O(q \log q)$，可处理 $q \leq 10^5$

暴力方法（小数据）

对于 $n, m \leq 300$ 的情况，可以直接用二维数组模拟，复杂度 $O(nm + q \cdot \max(n,m))$

实现细节

坐标处理技巧

• 将闭区间 $[x_1, x_2]$ 转化为左闭右开 $[x_1, x_2+1)$ 便于计算
• 离散化后，每个矩形的面积为 $(x_{i+1}-x_i) \times (y_{j+1}-y_j)$

交集计算优化

• 使用排序和双指针技巧快速计算线段交集
• 对横线、竖线分别按坐标排序，便于批量处理

边界情况

• 单个点的线（$x_1=x_2$ 且 $y_1=y_2$）
• 完全重叠的线段
• 斜线与边界相交的情况

总结

本题的核心在于：

1. 离散化思想：将无限平面转化为有限个关键点
2. 扫描线技术：高效处理一维区间覆盖问题
3. 容斥原理：正确处理多种操作的重叠部分
4. 分类讨论：针对不同特殊性质采用不同策略
5. 暴力巧妙应用：对少量斜线操作使用暴力法

这是一个典型的大规模数据处理问题，考察选手对离散化、扫描线、容斥原理等高级技巧的综合运用能力。