Matrix Data Structure Problem

Revision en1, by kaldiuo, 2018-09-09 07:34:54

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?

Tags matrix, #data structure, #advance data structures


  Rev. Lang. By When Δ Comment
en1 English kaldiuo 2018-09-09 07:34:54 378 Initial revision (published)