题解 | #【模板】二维差分#

// 记得在外围添加一圈0，差分可能会导致越界访问
// 初始模板一定要是全零，将初始数据以差分的形式添加，不能直接添加，会出错
// 详细看 61~67 行

// 添加一个数的差分：
//
//      -------------------
//      |(a,b)+k          |(a,d+1)-k
//      |                 |
//      |                 |
//      |            (c,d)|
//      |-----------------|
//       (c+1,b)-k          (c+1,d+1)+k
//

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> metrix;
vector<ll> arr;

ll n , m , q;

void metrix_set(ll a , ll b , ll c , ll d , ll e)
{
    metrix[a][b] += e;
    metrix[c+1][b] -= e;
    metrix[a][d+1] -= e;
    metrix[c+1][d+1] += e;
    return;
}

void metrix_build()
{
    for(ll i=1 ; i<=n ; i++)
    {
        for(ll j=1 ; j<=m ; j++)
        {
            metrix[i][j] += metrix[i][j-1] + metrix[i-1][j] - metrix[i-1][j-1];
        }
    }

    return;
}

int main()
{
    metrix.clear();
    scanf("%lld%lld%lld" , &n , &m , &q);
    fflush(stdin);

    metrix.resize((n+2) , vector<ll>((m+2) , 0));

    // n行 [0...n-1] --> [1...n]
    for(ll i=1 ; i<=n ; i++)
    {
        // m列 [0...m-1] --> [1...m]
        for(ll j=1 ; j<=m ; j++)
        {
            // scanf("%lld" , &metrix[i][j]);       ----------------> 初始模板一定要是全零，将初始数据以差分的形式添加，不能直接添加，会出错
            ll x;
            scanf("%lld" , &x);
            metrix_set(i , j , i , j , x);
        }
    }

    while(q--)
    {
        ll a , b , c , d , e;
        scanf("%lld%lld%lld%lld%lld" , &a , &b , &c , &d , &e);
        metrix_set(a , b , c , d , e);
    }

    metrix_build();

    for(ll i=1 ; i<=n ; i++)
    {
        for(ll j=1 ; j<=m ; j++)
        {
            printf("%lld " , metrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}