kaldiuo's blog

Matrix Data Structure Problem
By kaldiuo, history, 6 years ago, In English

I was thinking of this problem.

You have a matrix of size n by n (n<=10^5). You have to support q<=10^5 operations of 3 types (online):

  1. Given (i, l, r, x), set a[i][l...r] to x

  2. Given (l, r, x), set a[1...n][l...r] to x

  3. Given (i, l, r), find the minimum of a[i][l...r]

Is there any way to support these operations efficiently?

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

Comments Comments (5)
| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Sorry for my poor English.

  1. Let's store n dynamic tree segments with the operations horizontally interrupted.
  2. We will store the usual tree of segments with assignment on a segment for queries of the second type.

When a request of the third type comes, first update the i-th line through the second tree of segments for O (log n), and then answer the query through the first tree.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We can maintain n sets instead dynamic segment trees. In i-th set we store segment [l, r] if a[i][j1] == a[i][j2] for any l <= j1, j2 <= r and r — l is max possible.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

nvm

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think that the easiest way is swap columns and rows.

Now we could build segment tree, where we store for each row and for all column (last value, query index). Query j does one of the next things:

  • query of first type sets at every vertex on segment [left... right] pair (x, j) at index i;
  • query of second type sets at every vertex on segment [left... right] 'full column' value to (x, j);
  • third query takes minimum of last (by query index) between 'full column' and 'index' values at each vertex of the segment.

P.S. It seems that you need store list of 'lazy' queries for each vertex, that would be cleared after every update operation, so you would update only values that were not updated before.

→ Reply