题目链接:https://www.acwing.com/problem/content/800/
要睡觉了今早要早起,今晚再写关于二位差分的内容吧
放AC代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[1005][1005],b[1005][1005];//a前缀和数组,b差分数组 4 int n,m,q; 5 6 void insert(int x1,int y1,int x2,int y2,int c) 7 {//对b数组进行处理,即对a数组中(x1,y1)到(x2,y2)之间的元素+c 8 b[x1][y1]+=c; 9 b[x1][y2+1]-=c; 10 b[x2+1][y1]-=c; 11 b[x2+1][y2+1]+=c; 12 } 13 14 int main() 15 { 16 cin>>n>>m>>q; 17 for(int i=1; i<=n; i++) 18 for(int j=1; j<=m; j++) 19 cin>>a[i][j]; 20 //构造差分数组 21 for(int i=1; i<=n; i++) 22 for(int j=1; j<=m; j++) 23 insert(i,j,i,j,a[i][j]); 24 //对原数组进行操作 25 while(q--) 26 { 27 int x1,y1,x2,y2,c; 28 cin>>x1>>y1>>x2>>y2>>c; 29 insert(x1,y1,x2,y2,c); 30 } 31 //计算二维前缀和 32 for(int i=1; i<=n; i++) 33 for(int j=1; j<=m; j++) 34 b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1]; 35 //输出前缀和,即现在的s数组 36 for(int i=1; i<=n; i++) 37 { 38 for(int j=1; j<=m; j++) 39 { 40 cout<<b[i][j]<<" "; 41 } 42 cout<<endl; 43 } 44 return 0; 45 }