题解 | 【模板】二维差分

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2005;
// 改用 long long 避免数值溢出
long long a[N][N], d[N][N];

void insert(int x1, int y1, int x2, int y2, long long k, int n, int m) {
    x1 
= max(1, x1); y1 = max(1, y1);
    x2 
= min(n, x2); y2 = min(m, y2);
    if (x1 > x2 || y1 > y2) return;
    
    d
[x1][y1] += k;
    if (y2 + 1 <= m + 1) d[x1][y2 + 1] -= k;
    if (x2 + 1 <= n + 1) d[x2 + 1][y1] -= k;
    if (x2 + 1 <= n + 1 && y2 + 1 <= m + 1) d[x2 + 1][y2 + 1] += k;
}

int main() {
    ios
::sync_with_stdio(false);
    cin
.tie(nullptr);
    cout
.tie(nullptr);
    
    int n, m, q;
    // 确保只处理单组输入（题目中是单组输入，多组逻辑会导致重复输出）
    if (cin >> n >> m >> q) {
        memset(a, 0, sizeof(a));
        memset(d, 0, sizeof(d));
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin 
>> a[i][j];
                insert(i, j, i, j, a[i][j], n, m);
            }
        }
        
        while (q--) {
            int x1, y1, x2, y2;
            long long k;
            cin 
>> x1 >> y1 >> x2 >> y2 >> k;
            insert(x1, y1, x2, y2, k, n, m);
        }
        
        // 严格输出 n 行，每行 m 个元素
        for (int i = 1; i <= n; ++i) {
            bool first = true;
            for (int j = 1; j <= m; ++j) {
                a
[i][j] = d[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
                if (first) {
                    cout 
<< a[i][j];
                    first 
= false;
                } else {
                    cout 
<< " " << a[i][j];
                }
            }
            cout 
<< "\n";
        }
    }
    
    return 0;
}