高效解决大规模矩阵覆盖问题的二维差分与离散化方法

核心逻辑与数学原理

在大规模矩阵覆盖问题中，值域通常达到 $10^9$ 级别，而矩形数量 $N$ 相对较小（一般 $ ext{N} ext{≤} 10^3$）。若直接开辟全量二维阵列，内存必然爆栈。该问题的物理本质是连续空间的有限割裂与离散拓扑化。

核心逻辑由两层关键映射构成：第一层，坐标离散化（Coordinate Discretization）。通过对 $N$ 个矩形的横纵坐标分别进行去重和排序，将无限、稀疏的连续大平面，切割为最大 $(2N) imes (2N)$ 个紧凑的网格小块。每个网格在数值上代表一个特定大小的矩阵区域。

第二层，二维差分（2D Difference Grid）。在离散化后的紧凑网格矩阵上，利用容斥原理维护区间增量。将矩形区域覆盖的操作复杂度由 $O(X imes Y)$ 强行打压至 $O(1)$。最后，通过一次 $O(N^2)$ 的二维前缀和扫描还原网格状态，结合映射前的绝对坐标差值计算出最终覆盖面积。

状态设计与算法推导

1. 离散化网格切片拓扑

设第 $i$ 个矩形的左下角坐标为 $(x1_i, y1_i)$，右上角坐标为 $(x2_i, y2_i)$。收集所有 $x1_i, x2_i$ 存入集合 $X$，所有 $y1_i, y2_i$ 存入集合 $Y$。对 $X$ 和 $Y$ 排序并去重。去重后的集合大小分别为 $M_x$ 和 $M_y$。离散网格中的点 $(i, j)$ 对应原绝对坐标系中的点 $(X[i-1], Y[j-1])$。关键在于网格代表面积的映射：离散网格中的单元格 $(i, j)$（即右下角顶点为离散坐标第 $i$ 个 $X$、第 $j$ 个 $Y$ 的格子）在物理空间上代表的绝对面积为：

$$ \Delta S_{i, j} = (X[i] - X[i-1]) \times (Y[j] - Y[j-1]) $$

2. 二维差分状态转移

对于每个输入矩形，先利用二分检索（std::lower_bound）获取其左下角和右上角在离散集合中的 1-indexed 下标，设为 $(lx, ly)$ 和 $(rx, ry)$。该矩形覆盖的离散网格区间为 $x \in [lx+1, rx]$，$y \in [ly+1, ry]$。在二维差分矩阵 $D$ 上进行四点修正：

$$ D[lx+1][ly+1] \leftarrow D[lx+1][ly+1] + 1 $$

$$ D[rx+1][ly+1] \leftarrow D[rx+1][ly+1] - 1 $$

$$ D[lx+1][ry+1] \leftarrow D[lx+1][ry+1] - 1 $$

$$ D[rx+1][ry+1] \leftarrow D[rx+1][ry+1] + 1 $$

状态还原时，利用二维前缀和方程递推：

$$ S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + D[i][j] $$

若 @@@MATH_BLOCK31@@@，说明该离散网格被覆盖，将 $ \Delta S{i, j}$ 累加至总面积。

C++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 矩形结构体定义
struct Rectangle {
    int x1, y1, x2, y2;
};

void solveMatrixCoverage() {
    int n;
    if (!(cin >> n)) return;

    vector<Rectangle> rects(n);
    vector<int> xs, ys;
    xs.reserve(2 * n);
    ys.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
        xs.push_back(rects[i].x1);
        xs.push_back(rects[i].x2);
        ys.push_back(rects[i].y1);
        ys.push_back(rects[i].y2);
    }

    // 坐标离散化预处理
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    int mx = xs.size();
    int my = ys.size();

    // 致命踩坑点：差分矩阵的大小必须开到离散集合大小 + 2，防止四点修正时索引越界
    vector<vector<int>> d(mx + 2, vector<int>(my + 2, 0));

    for (int i = 0; i < n; ++i) {
        // 映射绝对坐标到离散化数组下标（0-indexed）
        int lx = lower_bound(xs.begin(), xs.end(), rects[i].x1) - xs.begin();
        int rx = lower_bound(xs.begin(), xs.end(), rects[i].x2) - xs.begin();
        int ly = lower_bound(ys.begin(), ys.end(), rects[i].y1) - ys.begin();
        int ry = lower_bound(ys.begin(), ys.end(), rects[i].y2) - ys.begin();

        // 关键点：将矩形覆盖转化为网格区间的端点修正，注意下标平移
        d[lx + 1][ly + 1] += 1;
        d[rx + 1][ly + 1] -= 1;
        d[lx + 1][ry + 1] -= 1;
        d[rx + 1][ry + 1] += 1;
    }

    long long total_area = 0;
    vector<vector<int>> s(mx + 1, vector<int>(my + 1, 0));

    // 二维前缀和还原并统计面积
    for (int i = 1; i <= mx; ++i) {
        for (int j = 1; j <= my; ++j) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + d[i][j];

            // 关键点：若前缀和大于 0，说明当前离散网格 [i-1, i]x[j-1, j] 被有效覆盖
            if (s[i][j] > 0 && i < mx && j < my) {
                long long width = xs[i] - xs[i - 1];
                long long height = ys[j] - ys[j - 1];
                total_area += width * height; // 致命踩坑点：大值域乘法计算必须强制采用 long long 转型
            }
        }
    }

    cout << total_area << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solveMatrixCoverage();

    return 0;
}

NOIP 实战避坑指南

面积乘法溢出与类型截断 即使输入的矩形坐标在一维离散化后下标很小（例如 $ ext{≤} 2000$），但在最终统计总面积时，width = xs[i] - xs[i - 1] 和 height = ys[j] - ys[j - 1] 依然是原始大值域下的绝对距离（最大可达 $10^9$）。如果直接写 total_area += width * height，由于 width 和 height 若未显式声明为 long long，编译器会优先按照 int 进行乘法运算，从而在赋值给 total_area 之前就已经发生整型截断溢出，导致结果输出负数或错误巨量值。
网格映射与点坐标错位 二维差分维护的是网格块（Cells）而非格点（Points）。很多选手在进行四点修正时，直接把二分查出来的点下标当做矩阵长宽去修改，即写成 d[lx][ly] += 1。这会导致差分还原后，污染了不该被覆盖的相邻网格。必须明确，离散化后第 $i$ 个位置和第 $i-1$ 个位置之间夹着的才是网格。因此，输入区间为 $[lx, rx]$ 的物理投影，对应的差分网格边界必须右移至 lx + 1 和 rx，否则会出现边界重叠计数错误。

经典 NOIP/洛谷真题

1. 洛谷 P2034 矩形覆盖 / 洛谷 P5490 【模板】扫描线

题意描述：给定平面上 $N$ 个两边平行于坐标轴的矩形，求这些矩形的总覆盖面积。矩形坐标值域 $[-10^9, 10^9]$，$N ext{≤} 10^3$（对离散化加差分法）或 $N ext{≤} 10^5$（对扫描线树结构）。
问题本质：大值域下的二维区间并集面积计算。
核心解题思路：当 $N ext{≤} 10^3$ 时，直接上本篇介绍的“二维差分+离散化”。将所有横纵坐标离散化为最大 $2000 imes 2000$ 的紧凑矩阵。利用二维差分 $O(1)$ 打标记，最后整体前缀和扫一遍。当 $N$ 扩展到 $10^5$ 级别时，二维差分空间复杂度 $O(N^2)$ 会 MLE，此时需要升级物理模型：将其中一维（如 $X$ 轴）离散化，另一维（$Y$ 轴）作为扫描线轴，从左到右动态维护一维线段树，将空间优化至 $O(N)$。

2. 洛谷 P4048 [AHOI2014] 骑士游戏

题意描述：在一个大矩阵地图上，有多个骑士发射不同覆盖范围的法术矩形，每个法术有其指定的伤害区域。同时有防御塔在特定点进行阻截。求某些关键矩阵区域被法术叠加覆盖的层数。
问题本质：大值域多矩形区域叠加层数的高频在线/离线查询。
核心解题思路：坐标范围极大，无法开辟原始阵列。由于所有的法术释放矩形和查询矩形在题目开始或离线状态下均已知，将所有法术边界及查询边界的 $X, Y$ 坐标全部抽离出来进行全局离散化。构建好紧凑网格后，使用二维差分数组对释放法术的区域执行四点增量操作（权重加 1）。预处理完所有法术后，对整个离散矩阵求二维前缀和，此时矩阵中每个位置的数值代表了该网格被法术覆盖的真实层数。最后，针对查询矩形，直接在已还原的前缀和矩阵上进行区域求和或最大值检索。