目 录CONTENT

文章目录

798. 差分矩阵.md

Gz
Gz
2022-03-10 / 0 评论 / 0 点赞 / 314 阅读 / 198 字 / 正在检测是否收录...

798. 差分矩阵(优化版本)

image-20220116193821750

#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N],b[N][N];


int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    //通过公式求出差分数组b
    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];

        }
    }
    //插值
    int x1,x2,y1,y2,c;
    while(q--){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        b[x1][y1] += c;
        b[x2+1][y1] -= c;
        b[x1][y2+1] -= c;
        b[x2+1][y2+1] += c;

    }
    //求前缀和
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1; j <= m ; j++){
            b[i][j] += b[i][j-1] + b[i-1][j] - b[i-1][j-1];
            printf("%d ",b[i][j]);
        }cout << endl;
    }

    
    return 0;
    
}
0

评论区