Luogu P3397 地毯

Walker_V · 2021-08-16 18:00:06 · 个人记录

Luogu P3397 地毯

一道二维差分的板子题。

因为二维差分比起一维的来说并不那么直观，所以这里主要讲一下二维差分的实现思路。

首先，记二维前缀和为 S_{a_{x,y}}= \sum^{x}_{i=1} \sum^{y}_{j=1} a_{i,j}；二维差分为 D_{x,y}。

显然，S_{a_{x,y}} 满足如下递推式：

S_{a_{x,y}}=S_{a_{x,y-1}}+S_{a_{x-1,y}}-S_{a_{x-1,y-1}}+a_{x,y}

这里，我们要用到一个性质：差分的前缀和为原数，即 S_{D_{x,y}}=a_{x,y}。

则代入二维前缀和的递推式，可以得到二维差分满足的关系式：

a_{x,y}=a_{x,y-1}+a_{x-1,y}-a_{x-1,y-1}+D_{x,y}

变形一下得到二维差分的计算式：

D_{x,y}=a_{x,y}-a_{x,y-1}-a_{x-1,y}+a_{x-1,y-1}

最后我们再来考虑如何实现题目中，修改一个左上角是 (x_1,y_1)，右下角是 (x_2,y_2) 的矩形区间。

类比前缀和的计算，不难得到：

D_{x_1,y_1} \gets D_{x_1,y_1}+1
D_{x_1,y_2+1} \gets D_{x_1,y_2+1}-1
D_{x_2+1,y_1} \gets D_{x_2+1,y_1}-1
D_{x_2+1,y_2+1} \gets D_{x_2+1,y_2+1}+1

即可。

代码实现如下：

#include<bits/stdc++.h>
#define N 1010

int n,m;
int map[N][N],d[N][N];

struct node {
    int x1,y1,x2,y2;
};

node a[N];

namespace WalkerV {
    void Read() {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) {
            scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
        }
        return;
    }

    void Solve() {
        for(int i=1;i<=m;i++) {
            d[a[i].x1][a[i].y1]++;
            d[a[i].x2+1][a[i].y1]--;
            d[a[i].x1][a[i].y2+1]--;
            d[a[i].x2+1][a[i].y2+1]++;
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                map[i][j]=map[i][j-1]+map[i-1][j]-map[i-1][j-1]+d[i][j];
            }
        }
        return;
    }

    void Print() {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                printf("%d%c",map[i][j],j==n?'\n':' ');
            }
        }
        return;
    }
}

int main()
{
    WalkerV::Read();
    WalkerV::Solve();
    WalkerV::Print();
    return 0;
}