题目传送门 首先介绍一下差分。给定一串数字序列：
1 3 2 4 5 7 6差分就是将序列的每一位与前一位做差得到的结果。
1 2 -1 2 1 2 -1 -6差分序列比原序列多一位（0减去最后一位）。 差分序列最重要的性质在于它的前缀和等于原序列。 回到题目，最朴素的想法是将每次给出的地毯范围内的数组元素++，但这么暴力的做法怎么想都会超时。而如果运用差分，我们便无须标记范围内的所有元素。对于用例
2 2 3 3我们可以对原数组做如下操作
0 0 0 0 0 1 0 -1 0 1 0 -1即只标记第一列（+1）和最后一列的后一列（-1），就可以在求前缀和时复原地毯的覆盖范围。 代码如下：
#include<cstdio> using namespace std; int n, m, Map[1005][1005], real[1005][1005], x1, y1, x2, y2; int main(void) { scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); for(int k=x1; k<=x2; k++) { Map[k][y1]++; Map[k][y2+1]--; } } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) real[i][j]=real[i][j-1]+Map[i][j]; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) printf("%d%c", real[i][j], (j==n?'\n':' ')); return 0; }