Top

二维差分数组


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int maxn=1e3+7;
int a[maxn][maxn],d[maxn][maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
}
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++){ //t次修改
int x1,y1,x2,y2,p;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&p);
d[x1][y1]+=p;d[x2+1][y2+1]+=p; //差分 左上右下加,左下右上减
d[x2+1][y1]-=p;d[x1][y2+1]-=p;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[i][j]+=d[i-1][j]+a[i][j-1]-a[i-1][j-1]; //差分前缀和
a[i][j]+=d[i][j]; //变换后的数组
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)printf("%d ",a[i][j]);
puts("");
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址