[11. two dimensional difference]

Two dimensional difference

Ideas :

• It is the same as the idea of one-dimensional difference , Let's take a look at my one-dimensional difference
• Assume that the two-dimensional difference group is b[][], In order to (x1,y1) It's the upper left corner ,(x2,y2) Add a to all elements of the submatrix in the lower right corner c.

The illustration

subject

Enter a nn That's ok mm The integer matrix of columns , Input again qq 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

Code

sample output ：

2 3 4 1
4 3 4 1
2 2 2 2

#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 ++)
           insert(i, j, i, j, a[i][j]);
           
           
   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]);
       }
           
       printf(" \n");
   }
}