Problem Statement
在 $n\times n$ 的格子上有 $m$ 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
第一行，两个正整数 $n,m$。意义如题所述。
接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。
Output
输出 $n$ 行，每行 $n$ 个正整数。
第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。
1
2
3
4
|
5 3
2 2 3 3
3 3 5 5
1 2 1 4
|
Sample Output
1
2
3
4
5
|
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
|
Explanation of example
覆盖第一个地毯后：
| $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$ |
Constraints
对于 $20%$ 的数据，有 $n\le 50$，$m\le 100$。
对于 $100%$ 的数据，有 $n,m\le 1000$。
Solving
二维差分和二维前缀和的板子题，时间复杂度可从O(N$^{3}$)优化到O(N$^{2}$)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int M = 0;
const int N = 10001;
int d[N][N];
int n,m;
int t;
struct node
{
int x1,y1,x2,y2;
}c[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
cin >> n >> m;
for(int i=1;i<=m;i++) cin >> c[i].x1 >> c[i].y1 >> c[i].x2 >> c[i].y2;
for(int i=1;i<=m;i++)
{
d[c[i].x1][c[i].y1]++;
d[c[i].x1][c[i].y2 + 1]--;
d[c[i].x2 + 1][c[i].y2 + 1]++;
d[c[i].x2 + 1][c[i].y1]--;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];//二维前缀和操作
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout << d[i][j] << " ";
}
cout << endl;
}
return 0;
}
|