P3397. 地毯

考点

  • 差分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50;
int n, m, a[maxn][maxn], b[maxn][maxn];

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

思路

二维差分的模板题,上《深进》截图。