AcWing 798. 差分矩阵

原题链接：https://www.acwing.com/problem/content/800/

参考之前的构造一维矩阵的思路（差分是前缀和的逆运算），假设数组是的前缀和矩阵，有以下等式成立： 将除了矩阵以外的所有项移到左边，就可以得到根据前缀和矩阵求出差分矩阵的等式： 构造出差分矩阵后，就可以根据一维差分的思想，来修改二维差分矩阵了。这个过程本质上用的也还是容斥原理。

#include<iostream>


#define N 1005

int a[N][N];
int b[N][N];

int n, m, q;

// 构建二维差分矩阵，本质是前缀和的逆运算
void build() {
    // a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i-1][j-1]
    // b[i-1][j-1] = a[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) {
            b[i-1][j-1] = a[i][j] - a[i][j-1] - a[i-1][j] + a[i-1][j-1];
        }
    }
}

// 根据最终b数组的结果更新a数组
void update() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i-1][j-1];
        }
    }
}


void input() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) a[i][0] = 0;
    for (int i = 1; i <= m; ++i) a[0][m] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
}

void output() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; ++j) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

int main() {
    
    input();
    build();
    int x1, y1, x2, y2, c;
    for (int i = 0; i < q; ++i) {
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
      	// 根据容斥原理
        b[--x1][--y1] += c;
        b[x2][y2] += c;
        b[x1][y2] -= c;
        b[x2][y1] -= c;
    }
    update();
    output();
}