洛谷 P3397：地毯 ← “二维前缀和 + 二维差分”模板题

【题目来源】
https://www.luogu.com.cn/problem/P3397

【题目描述】
在 n×n 的格子上有 m 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。

【输入格式】
第一行，两个正整数 n, m。意义如题所述。
接下来 m 行，每行两个坐标 (x1, y1) 和 (x2, y2)，代表一块地毯，左上角是 (x1, y1)，右下角是(x2, y2)。

【输出格式】
输出 n 行，每行 n 个正整数。
第 i 行第 j 列的正整数，表示 (i, j) 这个格子被多少个地毯覆盖。

【输入样例】
5 3
2 2 3 3
3 3 5 5
1 2 1 4

【输出样例】
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≤50，m≤100。
对于 100% 的数据，有 n,m≤1000。

【样例解释】

【算法分析】
● 暴力算法求解思路分析
时间复杂度为 O(n^3) 的算法，在算法竞赛中大约能处理规模为 1000 左右的数据不超时。
时间复杂度为 O(n^2) 的算法，在算法竞赛中大约能处理规模 ≤5000 左右的数据不超时。
本题数据规模很小，故采用时间复杂度较高的暴力算法求解时，也不会 TLE。

#include<iostream>
using namespace std;

const int maxn=1e3+5;
int a[maxn][maxn];

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

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

    return 0;
}

/*
in:
5 3
2 2 3 3
3 3 5 5
1 2 1 4

out:
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
*/

● 二维前缀和
（1）构建二维差分数组
一维“前缀和数组”预处理过程：sum[i]=sum[i-1]+a[i]
一维“区间和”计算过程：sum[y]-sum[x-1]      （y≥x）
类比于一维“前缀和数组”预处理过程及一维“区间和”计算过程，可知：
二维“前缀和数组”预处理过程：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
二维“区间和”计算过程：( sum[x2][y2] - sum[x2][y1-1] ) - ( sum[x1-1][y2] - sum[x1-1][y1-1] ) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]       （y2≥y1，x2≥x1）
（2）二维区域操作转端点操作
类比于一维区间操作转端点操作 d[le]+=x，d[ri+1]-=x，可以大大提升算法效率。可知，若二维区域的左上角坐标为 (x1, y1)，右下角坐标为 (x2, y2)，则如下代码可高效实现对此二维区域内所有元素 +1 的操作。

for(int i=x1; i<=x2; i++) {
    d[i][y1]++;
    d[i][y2+1]--;
}

推而广之，易得对二维区域内所有元素 +x 的代码为：d[i][y1]+=x，d[i][y2+1]-=x   （x1≤i≤x2）
（3）若已知差分数组 d[i][j]，则由语句 a[i][j]=a[i][j-1]+d[i][j]; 可得到原始数组。其中，i∈[1,n]。

【算法代码：二维前缀和 + 二维差分】

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

const int maxn=1e3+5;
int a[maxn][maxn];
int d[maxn][maxn];
int n,m;

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

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

    return 0;
}

/*
in:
5 3
2 2 3 3
3 3 5 5
1 2 1 4

out:
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
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145251582
https://blog.csdn.net/hnjzsyjyj/article/details/120617603
https://blog.csdn.net/hnjzsyjyj/article/details/120265452
https://www.luogu.com.cn/problem/solution/P3397
https://blog.csdn.net/qq_34988204/article/details/137672082