Queries on a Matrix
You are given Q queries, which contains 4 integers
a b c d.
where (a,b) is the TOP LEFT cell and (c,d) is the Bottom Right cell of a submatrix.
Now, all the cells of This submatrix has to be incremented by one.
After all the Q queries have been performed. Your task is to print the final resulting Matrix.
To understand this problem, first consider an easy problem. Suppose you have an array that contains all zeros. And you have questions to perform on it.
Each question gives us two signs L, R and we have to increase (inclusive) all the elements present in the boundary L.
If we use l to r for every question, then I ..... it will be really expensive. We need to think of a better approach.
Therefore, we create a differential array. Instead iterating all the values from l to r. We do this: A [L] ++; A [R + 1] -.We do this for all questions. And then finally,
Just iterate the array and calculate the array's prefix sum. For example: Initially, array 0 0 0 0 0 0 The first query occurs: (0, 3) array 1 0 0 0 -1 -1 0 The second query occurs: (1, 4) array 1 1 0 0 - 1 -1 is formed. The third query occurs: (2, 3) Array becomes 1 1 1 0 -2 -2.
Now, calculate the prefix sum of the array: 1 2 3 3 1 0 which is our final result. This approach is called "differential array". Now, in our original problem, we are given a matrix, and the query is on the sub matrix.
What we can do is we can apply the same differential array technique twice. Once for rows and another for columns.
We maintain 2 matrices named as row and call. For example: If query 1 1 2 3 means sub matrix (1,1) to (2,3) is incremented. In the row matrix we maintain the frequency of the row elements. While in the call matrix, we maintain the column wise frequency of the elements.
How will we maintain the frequency? --- By applying differential arrays on both matrices. Finally we need to compute prefix arrays individually for each row of the row matrix and each column of the column matrix.
And finally, our basic matrix will be calculated by computing suffix arrays from both rows and column matrices. See my code for more understanding :)
#include <bits/stdc++.h>
using namespace std;
int A[101][101];
int main() {
int t;
cin>>t;
while(t--)
{
int n,m,a,b,c,d;
cin>>n>>m;
memset(A,0,sizeof(A));
for(int i=0;i<m;++i)
{
cin>>a>>b>>c>>d;
A[a][b]++;
A[a][d+1]--;
A[c+1][b]--;
A[c+1][d+1]++;
}
for(int i=0;i<n;++i)
{
for(int j=1;j<n;++j)
A[j][i]+=A[j-1][i];
}
for(int i=0;i<n;++i)
{
cout<<A[i][0]<<" ";
for(int j=1;j<n;++j)
{
A[i][j]+=A[i][j-1];
cout<<A[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
