csp信奥赛C++高频考点专项训练之前缀和&差分 --【二维差分】：[USACO19FEB] Painting The Barn S

题目描述

农夫约翰不擅长多任务处理。他经常分心，很难完成长的项目。目前，他正试图在谷仓的一侧上漆，但他一直在画小矩形区域，然后由于照料奶牛的需要而偏离了方向，使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维 $x-y$ 平面，农夫约翰在该平面上绘制 $n$ 个矩形，每个矩形的边都与坐标轴平行，每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆，这样在不久的将来就不需要再重新粉刷了。但是，他不想浪费时间涂太多的油漆。结果表明，$K$ 涂层是最佳用量。请在他画完所有的长方形后，帮他确定谷仓有多少面积被 $K$ 层油漆覆盖。

输入格式

输入的第一行包含 $n$ 和 $K$。

其余 $n$ 行中的每一行包含四个整数 $x_1$、$y_1$、$x_2$、$y_2$，描述正在绘制的矩形区域，左下角 $(x_1,y_1)$ 和右上角 $(x_2,y_2)$。所有 $x$ 和 $y$ 值都在 $0$ 到 $1000$ 范围内，并且所有矩形都有正面积。

输出格式

请输出谷仓被 $K$ 层油漆覆盖的区域。

输入输出样例 1

输入 1

3 2
1 1 5 5
4 4 7 6
3 3 8 7

输出 1

8

说明/提示

$1\le K\le n\le 10^5$。

思路分析

本题要求计算平面上被恰好 $K$ 层油漆覆盖的面积。由于矩形边与坐标轴平行且所有坐标值在 $0$ 到 $1000$ 之间，可以将平面离散化为 $1000\times 1000$ 个 $1\times 1$ 的单位格子。每个格子代表一个面积单位，格子的坐标用其左下角整数点 $(i,j)$ 表示。

使用 二维差分 技术可以高效地处理矩形区域加一操作：

• 维护一个差分数组 a[1002][1002]，初始为全 $0$。

• 对于每个矩形 $(x_1,y_1,x_2,y_2)$，它覆盖的格子区域是 $x\in [x_1,x_2)$ 且 $y\in [y_1,y_2)$。在差分数组上执行：

  a[x1][y1] += 1
  a[x2][y1] -= 1
  a[x1][y2] -= 1
  a[x2][y2] += 1
  

  这个操作的作用是：对差分数组求二维前缀和后，区域 $[x_1,x_2)\times [y_1,y_2)$ 内的每个格子都会加上 $1$。

• 将差分数组通过两次扫描还原为原始覆盖次数：

  1. 行内前缀和：对每一行 $i$，从左到右累加 $a[i][j]+=a[i][j-1]$。此时每个 $a[i][j]$ 变成了该行从第 $0$ 列到第 $j$ 列的差分累积，即该行上 $y$ 方向的原始覆盖次数。
  2. 列前缀和：对每一列 $j$，从上到下累加 $a[i][j]+=a[i-1][j]$。这样每个 $a[i][j]$ 最终等于从 $(0,0)$ 到 $(i,j)$ 的二维前缀和，也就是格子 $(i,j)$ 上的实际油漆层数。

• 最后遍历所有格子 $(i,j)$，其中 $0\le i,j<1000$（因为矩形覆盖的 $x,y$ 范围是左闭右开，格子坐标对应 $x,y$ 坐标的下界），统计层数恰好为 $K$ 的格子数量，输出该数量即为所求面积。

时间复杂度 $O(1000^2+n)$，空间复杂度 $O(1000^2)$。

代码实现

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

int main() {
    int n, k; cin >> n >> k;
    int a[1002][1002] = {0}; // 差分数组，多开两行两列防止越界
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        a[x1][y1]++; // 左下角 +1
        a[x2][y1]--; // 右下角 -1
        a[x1][y2]--; // 左上角 -1
        a[x2][y2]++; // 右上角 +1
    }
    // 第一次扫描：按行做一维前缀和，恢复每行上的y方向覆盖次数
    for (int i = 0; i <= 1000; ++i)
        for (int j = 1; j <= 1000; ++j)
            a[i][j] += a[i][j-1];          // 每行从左到右累加
    // 第二次扫描：按列做一维前缀和，得到每个格子的最终覆盖层数
    for (int i = 1; i <= 1000; ++i)
        for (int j = 0; j <= 1000; ++j)
            a[i][j] += a[i-1][j];          // 每列从上到下累加
    int ans = 0;
    // 统计所有单位格子（i从0到999，j从0到999）
    for (int i = 0; i < 1000; ++i)
        for (int j = 0; j < 1000; ++j)
            if (a[i][j] == k) ans++;       // 恰好K层，面积+1
    cout << ans << endl;
    return 0;
}

功能分析

• 输入处理：读取 $n$ 和 $K$，随后循环读取 $n$ 个矩形的左下角 $(x_1,y_1)$ 和右上角 $(x_2,y_2)$。
• 差分构建：对每个矩形，在差分数组的四个角进行 +1 和 -1 操作，标记矩形区域在二维前缀和下的影响边界。
• 前缀和还原：
  • 第一轮按行累加，将每一行上的差分标记合并为该行上各列的实际覆盖次数。
  • 第二轮按列累加，将各行结果垂直合并，最终每个格子 $(i,j)$ 上的值等于从 $(0,0)$ 到 $(i,j)$ 的矩形区域内的所有差分标记总和，即原始油漆层数。
• 结果统计：遍历所有单位格子坐标 $0\le i,j<1000$，每当某个格子的覆盖层数等于 $K$ 时，答案加 $1$（因为每个格子面积恰好为 $1$）。
• 输出：打印统计得到的总面积。

---

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

---

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"##########  一站式掌握信奥赛知识!  ##########";
	cout<<"#############  冲刺信奥赛拿奖!  #############";
	cout<<"######  课程购买后永久学习，不受限制!   ######";
	return 0;
}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"跟着王老师一起学习信奥赛C++";
	cout<<"    成就更好的自己！       ";
	cout<<"  csp信奥赛一等奖属于你!   ";
	return 0;
}