地毯（二维差分，二维前缀和）

题目

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

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

输入格式

第一行，两个正整数n (1≤n≤1000)、m (1≤m≤105)，意义如题所述。

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

输出格式

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

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

输入样例

4 3

1 1 3 3

2 2 4 4 

3 1 4 3

输出样例

1 1 1 0

1 2 2 1

2 3 3 1

1 2 2 1

解题思路

定义二维数组a[][]以及它的差分数组b[][],改变差分数组b[][],再求b[][]的前缀和得到目标数组,即改变后的a[][].

C++实现

#include

using namespace std;

void cf(int x1, int y1, int x2, int y2,int k);//差分操作

int a[1010][1010], b[1010][1010];//声明二维数组及其差分数组

int main()
{
	int m, n,i,j;
	cin >> n >> m;
	

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			cf(i, j, i, j, a[i][j]);
	}

	while (m--) //输入地毯
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cf(x1, y1, x2, y2, 1);
	}

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];//求前缀和
			cout << a[i][j] << " ";
		}
		cout << endl;//每n个换行
	}

		return 0;
}

void cf(int x1, int y1, int x2, int y2,int k)
{
	b[x1][y1] += k;
	b[x1][y2 + 1] -= k;
	b[x2 + 1][y1] -= k;
	b[x2 + 1][y2 + 1] += k;
}