Acwing 798 two dimensional difference (difference matrix)

Enter a n That's ok m The integer matrix of columns , Input again q Operations , Each operation contains five integers x1,y1,x2,y2,c, among (x1,y1) and (x2,y2) Represents the upper left and lower right coordinates of a submatrix .

For each operation, add the value of each element in the selected sub matrix c.

Please output the matrix after all operations .

Input format
The first line contains integers n,m,q.

Next n That's ok , Each row contains m It's an integer , Represents an integer matrix .

Next q That's ok , Each row contains 5 It's an integer x1,y1,x2,y2,c, Represents an operation .

Output format
common n That's ok , Each row m It's an integer , Represents the final matrix after all operations are completed .

Data range
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤ The values of the elements in the matrix ≤1000
sample input ：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
sample output ：
2 3 4 1
4 3 4 1
2 2 2 2

effect ： Same as one-dimensional difference , We construct a two-dimensional difference fraction group to Let the original two-dimensional array a Add... To each element in the selected neutron matrix c The operation of , Can be O(n*n) The time complexity is optimized to O(1)

Two dimensional difference principle ： Same as one-dimensional difference , You need to construct a matrix b, Make primitive matrix a Is its prefix and matrix .

How to find ：
The core
b[x1][y1] + = c;
b[x1,][y2+1] - = c;
b[x2+1][y1] - = c;
b[x2+1][y2+1] + = c;

#include<iostream>
using namespace std;

const int N = 1010;
int a[N][N], b[N][N];
int n,m,q;

//  The core ,  Insert the function 
inline 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()
{
    
    cin >> n >> m >> q;
    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]);
        }
    for(int i=1;i<=q;i++)
    {
    
        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];  // The prefix and   Equal to the matrix to be solved later 
        }
        
    for(int i = 1; i<=n;i++)
    {
    
        for(int j=1;j<=m; j++)
        {
    
            cout << b[i][j] << " ";
        }
        cout << endl;
    }      
    return 0;
}