Блог пользователя kaldiuo

Автор kaldiuo, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +70
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

nvm

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.