Monitor

核心解题思路

这道题可以拆分为两个步骤：

构建覆盖图：将 $p$ 个监控器覆盖的矩形区域叠加到地图上。因为 $p$ 很大，我们不能一个个点去填，需要用 二维差分 将每次修改的复杂度降为 $O(1)$ 。
查询区域：对于 $q$ 个查询，我们需要快速判断一个矩形区域内的所有点是否都被覆盖。这可以通过 二维前缀和 实现 $O(1)$ 查询。

步骤一：标记监控区域 (二维差分)

我们定义一个二维数组 grid[n][m]。如果 grid[i][j] > 0，表示坐标 $(i, j)$ 被监控覆盖。

要在矩形 $(x_1, y_1)$ 到 $(x_2, y_2)$ 加上监控，利用二维差分性质，我们需要操作四个点：

grid[x1][y1]++
grid[x2+1][y1]--
grid[x1][y2+1]--
grid[x2+1][y2+1]++

所有修改完成后，对 grid 求一次二维前缀和，此时 grid[i][j] 就代表该点被多少个监控器覆盖。

步骤二：预处理查询 (二维前缀和)

查询要求是：矩形内所有点是否都被监控。

我们将 grid 转化为一个布尔矩阵（0/1矩阵）：

如果 grid[i][j] > 0，记为 1（被监控）。
如果 grid[i][j] == 0，记为 0（没被监控）。

然后对这个 0/1 矩阵再求一次二维前缀和，记为 sum[i][j]。

sum[i][j] 表示从 $(1,1)$ 到 $(i,j)$ 这个矩形内一共有多少个点被监控。

步骤三：回答查询

对于查询矩形 $(x_1, y_1)$ 到 $(x_2, y_2)$ ：

计算该矩形的理论总面积（格子数）： $Area = (x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ 。
利用前缀和数组 sum 快速计算该矩形内实际被监控的格子数：

$RealCount = sum[x_2][y_2] - sum[x_1-1][y_2] - sum[x_2][y_1-1] + sum[x_1-1][y_1-1]$
判断：如果 $RealCount == Area$ ，输出 YES，否则输出 NO。

复杂度分析

时间复杂度：
- 差分修改： $O(p)$
- 计算前缀和重建地图： $O(n \times m)$
- 查询： $O(q)$
- 总计： $O(n \times m + p + q)$ 。题目保证 $n \times m \le 10^7$ ，时间完全够用。
空间复杂度：需要存储地图， $O(n \times m)$ 。由于 $n \times m$ 较大，且 $n, m$ 只有总乘积限制，长宽不固定，建议使用 vector<vector<int>> 动态分配内存。

C++ 代码实现

C++

cpp

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, m;
    // 处理多组数据
    while (cin >> n >> m) {
        // 1. 初始化差分数组
        // 使用 vector 防止爆栈，且适应 n*m <= 10^7 的限制
        // 大小开 n+2, m+2 是为了方便处理边界 (1-based index) 和差分时的 +1 操作
        vector<vector<int>> grid(n + 2, vector<int>(m + 2, 0));

        int p;
        if (!(cin >> p)) break; 

        // 2. 读取监控并进行二维差分
        for (int i = 0; i < p; i++) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            grid[x1][y1]++;
            grid[x2 + 1][y1]--;
            grid[x1][y2 + 1]--;
            grid[x2 + 1][y2 + 1]++;
        }

        // 3. 计算每个点被覆盖的次数 (第一次前缀和)
        // 并同时将其转换为 0/1 状态进行第二次前缀和预处理
        // 为了节省空间，我们直接在 grid 上原地操作，或者开新数组
        // 这里为了逻辑清晰，我们在原数组上通过两步完成
        
        // 第一步：求差分的前缀和，还原每个位置的覆盖次数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
            }
        }

        // 第二步：将覆盖次数转换为 0/1，并计算 0/1 矩阵的前缀和
        // sum[i][j] 表示 (1,1) 到 (i,j) 矩形内有多少个点是被监控的
        // 注意：这里我们重用 grid 数组来存储 sum，节省空间
        // 我们需要倒序或者新开数组？不需要，直接按顺序处理即可，
        // 但要注意 grid[i-1][j] 此时已经是前缀和了，不能混用。
        // 为了代码最稳健，我们新开一个 sum 数组或者小心处理。
        // 鉴于内存限制 10^7 int 约为 40MB，开两个 vector 完全没问题。
        
        vector<vector<int>> sum(n + 2, vector<int>(m + 2, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int is_covered = (grid[i][j] > 0 ? 1 : 0);
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + is_covered;
            }
        }

        // 4. 处理查询
        int q;
        cin >> q;
        while (q--) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            // 计算该矩形内被监控的格子总数
            int covered_count = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
            
            // 计算该矩形的总面积
            int total_area = (x2 - x1 + 1) * (y2 - y1 + 1);

            if (covered_count == total_area) {
                cout << "YES" << "\n";
            } else {
                cout << "NO" << "\n";
            }
        }
    }
}

int main() {
    // IO 优化
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

图解说明

假设 3x3 的地图，有一个监控在 (1,1) 到 (2,2)。

初始差分操作：

grid[1][1]++, grid[3][1]--, grid[1][3]--, grid[3][3]++。
前缀和还原（还原后 grid 表示每个点的覆盖数）：

Plaintext
```
1 1 0
1 1 0
0 0 0
```

转为 0/1 并求前缀和 sum：

Plaintext

1 2 2  (第1行: 1, 1+1, 2+0)
2 4 4  (第2行: 1+1, 2+1+1-1, 2+0+2-0)
2 4 4  ...

查询：查询 (1,1) 到 (2,2)。

sum[2][2] 是 4。面积是 $(2-1+1)*(2-1+1) = 4$ 。相等 $\rightarrow$ YES。

易错点提示

内存限制： $n \times m$ 可达 $10^7$ ，直接开 int a[10000][10000] 会爆栈或爆内存（如果 $N=1, M=10^7$ ）。必须使用 vector 动态分配，或者一维数组模拟二维。
坐标系：题目是 1-based（从1开始），代码中数组开大一点（n+2），不仅处理了 1-based，还避免了差分 x2+1 越界的问题。
多组数据：题目说了包含多组测试数据，所以外层需要 while(cin >> ...) 循环，且每次循环内部要重新初始化 vector。

目录