thedebater's blog

Query on a matrix
By thedebater, history, 4 years ago, In English

We are given a matrix M of dimension N*N. All the cells are initially, zero. Also we 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.

I know the 1-D version of this problem. But I'm having difficulties implementing it in 2-D form. Any inputs regarding the same?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What r the constraint? I am not getting anything less than O(QN). Using prefix sum for each row.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

solution

i hope this helps you

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dont get why have we incremented at position mat[x2+1][y2+1]?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Mat[x1][y1]++; will increase from (x1,y1) => (n,n)

      Mat[x1][y2+1]--; will stop the increasing after column y2 So now from (x1,y1)=> (n,y2) will only be increased

      Mat[x2+1][y1]--; will stop the increasing after row x2 So now from (x1,y1) => (x2,n) will only be increased.

      But notice The rows after x2 got columns from y2+1 => n Which we already decreased from step 2

      And the columns after y2 got rows from x2+1 =>n Which we decreased from step 3

      So as you notice that the sub-rectangle (X2+1,y2+1) => (n,n) Will be decreased twice

      So we add mat[x2+1][y2+1]++;

      If you still having trouble Try drawing this test 5 1 2 2 4 4

      → Reply