原题链接：MJUPC-006_D.铺水泥

D.铺水泥

题目背景

某一天，小郭成为了人上人——包工头。这天，小郭给了打工人小马一张图纸，要求小马在给定的区域中铺水泥。不仅如此，还要求小马算出每个位置铺了多少次水泥。

题目描述

小郭的图纸中有 n × n n\times n n×n 个方格 , 又给了 m m m 块矩形区域。

问每个方格被铺了多少次水泥。

输入格式

第一行，两个正整数 n , m n,m n,m。

之后的 m m m 行，分别输入两个坐标 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 和 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)，代表这片区域被铺了一次的水泥地。其中，左上角是 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)，右下角是 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)。

输出格式

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

第 i i i 行第 j j j 列的正整数表示 ( i , j ) (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	0 0 0	0 0 0	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	1 1 1	1 1 1	0 0 0	0 0 0
0 0 0	0 0 0	0 0 0	0 0 0	0 0 0
0 0 0	0 0 0	0 0 0	0 0 0	0 0 0

第一、二次铺水泥后：

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

覆盖所有水泥后：

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

---

数据范围

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

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

【出题人】

Grape_L

题目解析：

题意即给你一个矩阵，求出矩阵每个格子被铺水泥的次数。本题有两种解法。

第一种：暴力

本题降低了难度，判定的数据比较小，可以用暴力的做法求解。即先建立一个二维数组 t t t ，来记录被铺的次数，再遍历一遍给的 n n n 行，每次将每个格子加 1 1 1 即可，最后输出二维数组 t t t 。

AC代码（C++）：

#include<iostream>
using namespace std; 
int t[1005][1005];

int main()
{
	int n, m, x1, x2, y1, y2;
	cin >> n >> m;
	for (int k = 1; k <= m; ++k)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = x1; i <= x2; ++i)
			for (int j = y1; j <= y2; ++j)
				++t[i][j];
	}//暴力模拟
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
			cout << t[i][j] << ' ';
		cout << endl;
	}
}

第二种（推荐做法）：差分&前缀和

假设 n n n 达到 10⁵ 甚至更大，暴力最坏的情况就是10³ *10³ * 10⁵ ，达到惊人的 10¹¹ ，复杂度为 O(m²n) ，必然超时。因此，我们需要更简便的方法解决它，这就是差分&前缀和。

前缀和，用于解决区间累加及查询问题。差分，是前缀和的逆运算，用于对数组进行快速多次的批量运算。本题可以搭配这两种算法解决问题。

差分&前缀和是重要的基础算法，它的复杂度只有 O(m*n)，较为高效地解决了这类问题，详细请看：前缀和&差分 详解、总结及例题。

除此之外，你问我还有没有更高效的？当然有！如果你数据结构和算法基础好的话，可以去了解一下二维树状数组和二维线段树，复杂度更低！

AC代码（C++）：

#include<iostream>
using namespace std;
int a[1005][1005] = { 0 }, d[1005][1005] = { 0 };
int main() {
	int n, m, x1, x2, y1, y2;
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		d[x1][y1] += 1, d[x2 + 1][y1] -= 1, d[x1][y2 + 1] -= 1, d[x2 + 1][y2 + 1] += 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a[i][j] += d[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
    return 0;
}