AcWing 798. 差分矩阵
原题链接
简单
作者:
longlongAC
,
2020-06-02 16:43:54
,
所有人可见
,
阅读 644
b[]的前缀和为a[] 所以可以根据a的前缀和公式求出差分数组b
b[]的加减C 可以求到前缀和的改变(可以画方块图理解)
还原前缀和数组 求b数组的前缀和即可
#include<bits/stdc++.h>
using namespace std;
const int N =1010;
int n,m,q;
int a[N][N],b[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++)
scanf("%d",&a[i][j]);
//构建差分数组B[i][j] a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i]; 推出 b[i][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++)
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
while(q--)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
b[x1][y1] +=c; //b[x1][y1]+=c 右下角所有矩阵的前缀和就都加上了C
b[x2+1][y1] -=c; //减去第一步b[x1][y1] 下方所有矩阵的前缀和多加的c
b[x1][y2+1] -=c; //减去第一步b[x1][y1] 右边所有矩阵的前缀和多加的c
b[x2+1][y2+1] +=c; //加上第二第三步多减去的部分c 注意这里加减C是对后面求前缀和产生影响
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j] =b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j]; //求前缀和 前缀和数组就是所求
for(int i=1;i<=n;i++) //输出前缀和数组
{
for(int j=1;j<=m;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
谢谢
点赞