地毯

链接

这题需要用二维差分解决,这里有一个很巧妙的方法

我们需要对n x m的数据进行加减,可以修改n+1 x m+1 的四个角,再进行求和即可修改

具体做法: 假设修改1,1到 6,7的值,都加上c, 我们只需令1,1和7,8的值加上c,而1,8和7,1的值减c

这样我们通过修改4个值从而对n x m的值进行了修改

#include<iostream>
using namespace std;
int diff[1002][1002] = { 0 };
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		diff[x1][y1] += 1;
		diff[x2 + 1][y2 + 1] += 1;
		diff[x1][y2 + 1] -= 1;
		diff[x2 + 1][y1] -= 1;
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			diff[i][j] = diff[i][j] + diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
			cout << diff[i][j] << " ";
		}
		cout << endl;
	}
}

时间复杂度:O(n²)

空间复杂度:O(n²)