洛谷题单指南-前缀和差分与离散化-P3397 地毯

原题链接：https://www.luogu.com.cn/problem/P3397

题意解读：给定一个n*n的矩阵，每个元素初始值为0，再将m个子矩阵中的元素都增加1，统计每个元素最终的值。

解题思路：

1、暴力法

枚举每一个子矩阵，将对应元素值加1，时间复杂度为1000^3，不可行。

2、二维差分

对于给定二维数组s[][]，给指定区间左上角(x1,y1)右下角(x2,y2)每一个元素增加z，可以借助二维差分完成。

什么是二维差分？

可以理解为二维前缀和的逆运算，设s[][]为a[][]的二维前缀和数组，那么a[][]就是s[][]的差分数组。

如何计算二维差分？

如图所示，矩阵每个格子代表a[][]，有颜色的区块代表前缀和s[][]，红色区域为s[i][j]，绿色区域为s[i-1][j]，蓝色区域为s[i][j-1]，黑色区域为s[i-1][j-1]

要计算a[i][j]，则有a[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1]

如何给数组s[][]指定区间左上角(x1,y1)右下角(x2,y2)每一个元素增加z？

如图所示，矩阵每个元素表示a[][]，要给前缀和数组s[][]区间(x1,y1)(x2,y2)每个元素增加z

第一步：a[x1][y1] += z，这样一来，红色区域内所有的s[][]都增加了z

第二步：a[x2+1][y1] -= z，这样一来，蓝色区域内的所有s[][]都减去了z

第三步：a[x1][y2+1] -= z，这样一来，绿色区域内所有的s[][]都减去了z

第四步：a[x2+1][y2+1] += z，这样一来，蓝色区域、绿色区域、黄色区域内所有的s[][]都保持不变，既不增加z又不减少z

此时，黑色区域内的s[][]都增加了z，即(x1,y1)(x2,y2)区域的每一个s[][]都增加了z

以上操作时间复杂度为O(1)。

3、完整流程

第一步：计算二维差分数组(由于初始数组元素都是0，因此差分数组元素也是0，此步骤可以省去)

第二步：通过二维差分数组，执行区间元素加1操作

第三步：通过二维前缀和还原数组

第四步：输出答案

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m;
int s[N][N], a[N][N];

int main()
{
    cin >> n >> m;
    int x1, y1, x2, y2;
    for(int i = 1; i <= m; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        a[x1][y1] += 1;
        a[x2 + 1][y1] -= 1;
        a[x1][y2 + 1] -= 1;
        a[x2 + 1][y2 + 1] += 1;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
            cout << s[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}