AcWing 798. 差分矩阵
原题链接
简单
作者:
无双飞怪
,
2024-04-17 17:12:37
,
所有人可见
,
阅读 1
这题二维差分略显抽象 但差分的实质不就是求前缀和时后面的不受影响吗
注:求前缀和时后面的不受影响(就是当前的数不会累加到下一个数里) 前缀和s[i]==a[i]这就是差分
后面的不受影响 所以这里在处理一个数时把下面右面的数都减去了 这就保证了求前缀和时后面的不受影响 只影响a[i][j]这一个 这便是差分
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1010;
const int inf=0x3f3f3f3f;
int n,m,q;
int a[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
a[i][j]+=x;//这个意思是只给你自己加x
a[i+1][j]-=x;//下面的及下下面及下下下……面不受影响(往右下角看
a[i][j+1]-=x;
a[i+1][j+1]+=x;
}
}
while(q--)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
a[x1][y1]+=c;
a[x2+1][y1]-=c;
a[x1][y2+1]-=c;
a[x2+1][y2+1]+=c;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//这里是求前缀和
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",a[i][j]);
puts("");
}
return 0;
}