覆盖

GitHub跳转原题关系图返回列表

先用差分统计有多少行和多少列被覆盖，再用容斥计算最终被打扫的方格数。

OJ: luogu

题目 ID: P2692

难度:普及-

标签:差分容斥模拟

日期: 2026-06-19 01:15

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有一个 N × M 的方格矩阵。

  • 每个男生负责一段连续的行，也就是把这些行的所有格子都覆盖
  • 每个女生负责一段连续的列，也就是把这些列的所有格子都覆盖

问最后至少被覆盖一次的格子总数是多少。

思路

先看最直接的做法：

真的开一个二维矩阵，把男生负责的整行、女生负责的整列全部涂色，最后统计有多少格被涂过。

这个思路最容易理解，也适合当对拍程序：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m, b, g;
int vis[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> b >> g;

    for (int i = 1; i <= b; i++) {
        int l, r;
        cin >> l >> r;
        for (int row = l; row <= r; row++) {
            for (int col = 1; col <= m; col++) {
                vis[row][col] = 1;
            }
        }
    }

    for (int i = 1; i <= g; i++) {
        int l, r;
        cin >> l >> r;
        for (int col = l; col <= r; col++) {
            for (int row = 1; row <= n; row++) {
                vis[row][col] = 1;
            }
        }
    }

    int ans = 0;
    for (int row = 1; row <= n; row++) {
        for (int col = 1; col <= m; col++) {
            ans += vis[row][col];
        }
    }

    cout << ans << '\n';

    return 0;
}

但正式做法没必要真的建整个棋盘。

因为一个格子是否被覆盖，只取决于：

  • 它所在的行是否被某个男生覆盖
  • 或者它所在的列是否被某个女生覆盖

所以我们先分别算：

  • 有多少行被覆盖，记作 R
  • 有多少列被覆盖，记作 C

这里可以用一维差分处理区间覆盖：

  • 男生的每个区间只影响行
  • 女生的每个区间只影响列

最后再做一次容斥：

  • 被覆盖的行一共贡献 R × M 个格子
  • 被覆盖的列一共贡献 C × N 个格子
  • 同时属于覆盖行和覆盖列的格子被算了两次，一共有 R × C 个，要减掉

所以答案是：

R × M + C × N - R × C

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;

int n, m, b, g;
int diff_row[MAXN], diff_col[MAXN];

int count_covered(int limit, int diff[]) {
    int covered = 0;
    int sum = 0;

    for (int i = 1; i <= limit; i++) {
        sum += diff[i];
        if (sum > 0) {
            covered++;
        }
    }

    return covered;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> b >> g;

    for (int i = 1; i <= b; i++) {
        int l, r;
        cin >> l >> r;
        diff_row[l]++;
        diff_row[r + 1]--;
    }

    for (int i = 1; i <= g; i++) {
        int l, r;
        cin >> l >> r;
        diff_col[l]++;
        diff_col[r + 1]--;
    }

    long long covered_row = count_covered(n, diff_row);
    long long covered_col = count_covered(m, diff_col);

    // 容斥：被覆盖的行全部算一次，被覆盖的列全部算一次，
    // 同时属于覆盖行和覆盖列的格子被重复统计，需要减掉。
    long long ans = covered_row * m + covered_col * n - covered_row * covered_col;
    cout << ans << '\n';

    return 0;
}

复杂度

时间复杂度是 O(N+M+B+G)O(N + M + B + G)，空间复杂度是 O(N+M)O(N + M)。

总结

这题的关键是不要把注意力放在“二维棋盘”上，而是先拆成“哪些行被覆盖、哪些列被覆盖”。

一旦拆开，剩下就是一维差分和简单容斥。