P5542 [USACO19FEB] Painting The Barn S

GitHub返回列表

OJ: luogu

题目 ID: P5542

标签: 二维差分二维前缀和

日期: 2026-05-31 14:51

目录

  1. 题目解析
    1. 题意
    2. 思路
    3. 复杂度
    4. 注意
  2. 代码

题目解析

题意

在 1000×10001000 \times 1000 的网格上画 nn 个边平行于坐标轴的矩形，每个矩形由左下角和右上角坐标 (x1,y1,x2,y2)(x_1,y_1,x_2,y_2) 给出。求有多少个单位面积被恰好 KK 层油漆覆盖。

思路

核心：二维差分 + 二维前缀和

坐标范围只有 0∼10000 \sim 1000，网格非常小，可以直接开 1001×10011001 \times 1001 的数组。

对每个矩形做 O(1)O(1) 的差分标记：

  • diff[x1][y1]++
  • diff[x1][y2]--
  • diff[x2][y1]--
  • diff[x2][y2]++

最后跑一遍二维前缀和，还原每个格子 (i,j)(i,j)（即单位面积 [i,i+1)×[j,j+1)[i,i+1) \times [j,j+1)）被覆盖的次数，统计等于 KK 的个数即可。

复杂度

  • 时间：O(n+10002)O(n + 1000^2)
  • 空间：O(10002)O(1000^2)

注意

  • 统计时 i,ji,j 只遍历 0∼9990 \sim 999，因为只有这些格子有面积
  • 差分数组大小为 1002×10021002 \times 1002 防越界

代码

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

const int MAX = 1000;
int diff[1002][1002];

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

    int n, K;
    cin >> n >> K;

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 二维差分：对矩形区域 [x1,x2) × [y1,y2) 全部 +1
        diff[x1][y1]++;
        diff[x1][y2]--;
        diff[x2][y1]--;
        diff[x2][y2]++;
    }

    int ans = 0;
    for (int i = 0; i <= MAX; i++) {
        for (int j = 0; j <= MAX; j++) {
            // 二维前缀和，还原每个单位格子的油漆层数
            if (i > 0) diff[i][j] += diff[i - 1][j];
            if (j > 0) diff[i][j] += diff[i][j - 1];
            if (i > 0 && j > 0) diff[i][j] -= diff[i - 1][j - 1];
            // 格子 [i,i+1)×[j,j+1) 有面积，只统计 i,j < MAX
            if (diff[i][j] == K && i < MAX && j < MAX) ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}