如y总所言
如图,我们只想让对应的a数组(x1,y1)和(x2,y2)形成的矩形内的每个点加上c
只要在b中的(x1,y1)加c,以(x1,y1)为左上角的大矩形里的点都会加上c
我们还要让打三角符号的点减c,对应的区域的点都会减c,但(x2 + 1,y2 + 1)的矩形里的点多减了一次
让那个点加上c就行了
这里比较难以理解的是为什么要进行insert(i,j,i,j,a[i])这个操作
这个操作目的是当a不再是0时,使得b仍然是a的差分数组,即维持a,b间的关系
这个操作前提是b已经是a的差分数组
我们知道当b是a的差分数组时,某个a[i][j]进行了加法操作(比如加上c),如果这时b不改变,那么b将不再是a的差分数组
所以就要对b[i][j]进行一次insert(i,j,i,j,c)操作,只对(i,j)这个点有影响,这个操作过后,当我们求b的(i,j)这个点的前缀和时
得到的就是原来的a[i][j]加上c的值,这时b就仍然是a的差分数组。
由于刚开始a,b都是0,b就是a的差分数组,当读入a[i][j]时,相当于a[i][j]加上了某一个数,这时要想让b仍然是a的差分数组,就要进行insert(i,j,i,j,a[i][j])操作
代码
#include<iostream>
using namespace std;
const int N = 1e3+5;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
b[x1][y1] += c;
b[x1][y2+1] -= c;
b[x2+1][y1] -= c;
b[x2+1][y2+1] += c;
}
int main(){
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d",&a[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
insert(i,j,i,j,a[i][j]);/*对b进行插入操作,使得b仍然是a的差分数组,以便进行下面的操作*/
while(q--){
int x1,y1,x2, y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i = 1; i <= n; i++)/*计算前缀和,注意到b数组(i,j-1)这个点的前缀和就是a[i][j-1],以此类推*/
for(int j = 1; j <= m; j++)
a[i][j] = b[i][j] + a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}
牛啊
周某键盘颜色咋搞的呀
游戏键盘&机械键盘
终于懂了ij,ij,aij
这一步,谢谢
%%%