P3397 铺地毯数个数（初识差分）

地毯

题目描述

在 $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

提示

样例解释

覆盖第一个地毯后：

覆盖第一、二个地毯后：

覆盖所有地毯后：

数据范围

对于 $20%$ 的数据，有 $n\le 50$，$m\le 100$。

对于 $100%$ 的数据，有 $n,m\le 1000$。

解法

差分

数组的特殊描述方式

对于一维数组：
0 1 1 1 1 1 0
可以使用：

-------------->相加
0 +1 0 0 0 -1 0
-------------->相加

的方式描述
同理，对于二维数组：

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

可以使用

-------------->相加
| 0 0 0 0 0
| 0 +1 0 0 -1
| 0 0 0 0 0
| 0 0 0 0 0
| 0 -1 0 0 +1
*
相加

的方式来描述。
对于其中某一个元素，可以采用该格子左上角所有矩形框元素之和。例如差分表如下：

0 0 0 | 0 0
0 1 2 | 1 0
0 3 x | 1 0
-------
0 1 1 | 1 0
0 0 0 | 0 0

那么x =1 + 2 + 3，由此可以发现如果得知原表x当前（差分值）、左边（原表值）、上边（原表值）、左上边（原表值）的数，则可以求出来原表当前元素值。
具体公式为：

arr[i][j] = input_arr[i][j]
            + arr[i-1][j]
            + arr[i][j-1]
            - arr[i-1][j-1]

对于- arr[i-1][j-1]是为了减去重复的部分。
见图:

1. A原 = A差 + B原 + C原 - BC重复
2. 减去重复的红色阴影部分（BC重复）。
   题解：

#include <stdio.h>

int arr[1001][1001];        // 存储最终结果的矩阵
int input_arr[1001][1001];   // 差分矩阵
int n = 0, m = 0;

void input() {
    int x1, x2, y1, y2;
    scanf("%d %d", &n, &m);  // 读入 n 和 m
    for (size_t i = 0; i < m; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        input_arr[x1][y1]++;         // 左上角 +1
        input_arr[x1][y2+1]--;       // 右上角下方 -1
        input_arr[x2+1][y1]--;       // 左下角右方 -1
        input_arr[x2+1][y2+1]++;     // 右下角 +1
    }
}

void output() {
    // 通过前缀和计算每个格子被覆盖的次数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 计算二维前缀和
            arr[i][j] = input_arr[i][j] 
                        + (i > 1 ? arr[i-1][j] : 0)
                        + (j > 1 ? arr[i][j-1] : 0)
                        - (i > 1 && j > 1 ? arr[i-1][j-1] : 0);
        }
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

int main() {
    input();   // 输入地毯信息
    output();  // 输出每个点被覆盖的次数
    return 0;
}