kaldiuo's blog

By kaldiuo, history, 12 months 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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont know, it is correct or no, but it is my idea:

Change 2nd type of query, to n times of 1st query. And we will use sqrt decomposition. We divide queries to K blocks. And recalc after each block. And find answer will not be hard

Sorry, for my poor english

»
12 months 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.

  • »
    »
    12 months 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.

»
12 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

nvm

»
12 months 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.