二维差分·学习备忘录

cnblogs 2024-08-13 08:09:13 阅读 94

二维差分

为什么我为OI泪目?因为我菜得离谱......

引入

一维差分用来O(1)修改区间,配合上一维前缀和就是O(N)的查询区间和。

差分为前缀和的逆运算。

二维差分同理。

接下来这道题就用二维差分来解决。

\(例题:地毯>>\)

地毯

题目描述

\(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

<code>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

提示

样例解释

覆盖第一个地毯后:

\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)

覆盖第一、二个地毯后:

\(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(2\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(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\)

题解

康康数据范围,\(n<=1000\),暴力修改\(O(n^ 2)\),共有\(O(m)\)次修改,总共\(O(n^2*m)=1e9\)复杂度,洛谷能够过,但\(CCF\)肯定会把你卡死。

于是出现吧:二维差分!

首先拿来一张图,要让红色部分+1,如何\(O(1)\)解决?

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0(x1,y1) 0 0

0 0 0(x2,y2) 0

0 0 0 0

差分是为了后面的前缀和做准备

我们先给\((x1,y1)+1\),可以达成增加的目的,但事情就会成这样(前缀和之后)

0 0 0 0

0 1 1 1

0 1 1 1

0 1 1 1

很显然,蓝,绿,棕四个部分都是被多加了的

于是我们再给\((x1,y2+1)-1,(x2+1,y1)-1\)来抵消影响。

但……

0 0 0 0

0 1 1 0

0 1 1 0

0 0 0 -1

这里会被减两遍

再给其+1就OK

如果遇到差分数组要初始化的情况,例如第2题,我们就将它当做边长为1的矩形差分处理即可。

CODE

<code>#include<bits/stdc++.h>

using namespace std;

const int tsn=1e3+5;

int n,m;

int qz[tsn][tsn];

int sum[tsn][tsn];

int main()

{

#ifndef ONLINE_JUDGE

freopen("00in.txt","r",stdin);

freopen("00out.txt","w",stdout);

#endif

cin>>n>>m;

for(int i=1;i<=m;i++)

{

int a1,b1,a2,b2;

cin>>a1>>b1>>a2>>b2;

qz[a1][b1]++,qz[a1][b2+1]--,qz[a2+1][b1]--,qz[a2+1][b2+1]++;

}

// for(int i=1;i<=n;i++,cout<<endl)

// for(int j=1;j<=n;j++)

// cout<<qz[i][j]<<" ";cout<<endl;

for(int i=1;i<=n;i++,cout<<endl)

for(int j=1;j<=n;j++)

sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+qz[i][j],cout<<sum[i][j]<<" ";

return 0;

}



【模板】二维差分

题目描述

给你一个n行m列的矩阵,下标从1开始。

接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k

表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k,

请输出操作后的矩阵。

输入格式

第一行包含三个整数\(n,m,q\).

接下来\(n\)行,每行\(m\)个整数,代表矩阵的元素

接下来\(q\)行,每行5个整数\(x1, y1, x2, y2, k\),分别代表这次操作的参数

输出格式

输出n行,每行m个数,每个数用空格分开,表示这个矩阵。

样例 #1

样例输入 #1

2 3 4

1 2 3

4 5 6

1 1 2 2 3

1 2 2 3 -1

1 1 1 3 4

1 1 2 1 1

样例输出 #1

9 8 6

8 7 5

提示

\(1≤n,m≤1000\)

\(1≤q≤10^5\)

\(1≤x1≤x2≤n\)

\(1≤y1≤y2≤m\)

\(−10^9≤矩阵中的元素≤10^9\)

\(−10^5≤k≤10^5\)

分析

注意一下上文,对你来说不是难事。

CODE

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int tsn=1e3+5;

int n,m,q;

int a[tsn][tsn];

int cf[tsn][tsn];

int sum[tsn][tsn];

void _cf(int a1,int b1,int a2,int b2,int k)

{

cf[a1][b1]+=k,

cf[a2+1][b1]-=k,

cf[a1][b2+1]-=k,

cf[a2+1][b2+1]+=k;

}

signed main()

{

#ifndef ONLINE_JUDGE

freopen("00in.txt","r",stdin);

freopen("00out.txt","w",stdout);

#endif

int n,m,q;

cin>>n>>m>>q;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

cin>>a[i][j],_cf(i,j,i,j,a[i][j]);

while(q--)

{

int a1,b1,a2,b2,k;

cin>>a1>>b1>>a2>>b2>>k;

_cf(a1,b1,a2,b2,k);

}

for(int i=1;i<=n;i++,cout<<endl)

for(int j=1;j<=m;j++)

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+cf[i][j],cout<<sum[i][j]<<" ";

return 0;

}

完结撒❀

在这里插入图片描述

在这里插入图片描述

图片来自网络。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。