企业官网建设流程全解析

二维差分算法模版——— AcWing 798. 差分矩阵

#include <iostream> using namespace std; const int N = 1010; int n, m, q; int a[N][N], b[N][N]; void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main() { scanf("%d%d%d", &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 ++ ) //相当于先将b数组看为0，再进行视为方块为一个数的加减操作 insert(i, j, i, j, a[i][j]);//因为无法直接初始化b，只能逆着来 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 ++ ) for (int j = 1; j <= m; j ++ ) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]); puts(""); } return 0; }