当前位置：首页 > news >正文

《洛谷深入浅出进阶篇》P3397 地毯————二维差分

news 来源：原创 2024/5/20 23:57:47

上链接：P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3397

上题干：

题目描述

在 n×n 的格子上有 m 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 n,m。意义如题所述。

接下来 m 行，每行两个坐标 (x1,y1) 和 (x2,y2)，代表一块地毯，左上角是 (x1,y1)，右下角是(x2,y2)。

输出格式

输出 n 行，每行 n 个正整数。

第 i 行第 j 列的正整数表示 (i,j) 这个格子被多少个地毯覆盖。

输入输出样例

输入 #1复制
5 3
2 2 3 3
3 3 5 5
1 2 1 4
输出 #1复制
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1
说明/提示

样例解释

覆盖第一个地毯后：

0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

覆盖第一、二个地毯后：

0 0 0 0 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

覆盖所有地毯后：

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

数据范围

对于 20% 的数据，有 n≤50，m≤100。

对于 100% 的数据，有 n,m≤1000。

0	0	0	0	0
0	1	1	0	0
0	1	1	0	0
0	0	0	0	0
0	0	0	0	0

0	0	0	0
1	1	0	0
1	2	1	1
0	1	1	1
0	1	1	1

1	1	1	0
1	1	0	0
1	2	1	1
0	1	1	1
0	1	1	1

在上一篇已经讲过了差分是什么，和一维差分：

《洛谷深入浅出进阶篇》 P2367语文成绩——差分-CSDN博客https://blog.csdn.net/louisdlee/article/details/134400596 这章的内容来介绍一下，二维差分。

假设b[i,j]为差分数组，a[i,j]为原数组

b[i,j]和a[i,j]满足下面这个性质：

$\sum_{i=1}^{n}\sum_{j=1}^{m}b_{i,j}=a_{i,j}$

（只要是差分就应该满足这个性质）

但是根据题目的不同，差分数组的求法也有所不同

但是我们求答案的时候一定要记住四个字：前加后减

给大家举几个例子理解：

假设这是第一块地毯（原数组），

1	2	3
2	1	1
3	1	1
4	0	0
5	0	0

那么它的差分数组可以是这样的。

1	2	4
2	1	-1
3	1	-1
4	0	0
5	0	0

假设这是第二块地毯：

0	0	0
0	0	0
1	1	1
1	1	1
1	1	1

那么它的差分数组我想你们应该可以想到了吧：（加了一列虚拟边界来表示，其实我们真实遍历的时候不会扫描到n*m之外的格子）

1	3	6
2	0	0
3	1	-1
4	1	-1
5	1	-1

我们发现：

-1的位置都是在原来矩阵的后面一列，

假设左上角为(x1,y1) 右下角为(x2,y2)

那么第一列的-1应该在 (x1,y2+1)处

第二列的-1应该在(x1+1,y2+1)处

因为我们加了虚拟边界，当-1出现在原来的边界外的时候，也不用担心。

上代码：

const int N = 1e3 + 10;
int a[N][N];
int b[N][N];
int main()
{int n, m;cin >> n >> m;while (m--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;for (int i = x1; i <= x2; i++){b[i][y1]++;b[i][y2 + 1]--;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){b[i][j] += b[i][j - 1];cout << b[i][j] << ' ';}cout << endl;}
}