題目難度：普及一
題目傳送門

地毯

題目描述

在 $n\times n$ 的格子上有 $m$ 個地毯。

給出這些地毯的信息，問每個點被多少個地毯覆蓋。

輸入格式

第一行，兩個正整數 $n,m$。意義如題所述。

接下來 $m$ 行，每行兩個坐標 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一塊地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

輸出格式

輸出 $n$ 行，每行 $n$ 個正整數。

第 $i$ 行第 $j$ 列的正整數表示 $(i,j)$ 這個格子被多少個地毯覆蓋。

樣例 #1

樣例輸入 #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$	$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$

---

數據范圍

對于 $20\%$ 的數據，有 $n\le 50$，$m\le 100$。

對于 $100\%$ 的數據，有 $n,m\le 1000$。

題目分析：這題數據太水，打暴力都能AC，時間復雜度為O（m*n^2)可以過。

暴力代碼：

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1100;int a[N][N];
int n,m;ll read()
{ll s=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}int main() {n = read(),m = read();for(int i = 1; i <= m; i++){int x1 = read(), y1 = read(),x2 = read(),y2 = read();for(int x = x1; x <= x2; x++){for(int y = y1; y <= y2; y++) a[x][y]++;}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)  cout<<a[i][j]<<' ';cout<<'\n';}	   return 0;
}
*下面介紹下法二：**二維差分***
代碼部分：```cpp#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1100;int a[N][N],b[N][N];
int n,m;void insert(int x1,int y1,int x2,int y2,int c)
{b[x1][y1] += c;b[x1][y2 + 1] -= c;b[x2 + 1][y1] -= c;b[x2 + 1][y2 + 1] += c;
}ll read()
{ll s=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}int main() {n = read(),m = read();for(int i = 1; i <= m; i++){int x1 = read(), y1 = read(),x2 = read(),y2 = read();insert(x1,y1,x2,y2,1);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)  {b[i][j] += b[i - 1][j] + b[i][j - 1]-b[i - 1][j - 1];cout<<b[i][j]<<' '; }cout<<'\n';}	   return 0;
}