RMQ with lazy updates
Difference between en2 and en3, changed 0 character(s)
I want a data structure(range maximum query with lazy updates) that supports 2 queries. One of them is an update in which we update all the elements from position $l$ to $r$ to be equal to $k$. The second query is getting the index of the maximum element in the range $[l, r]$. For the second query, if there are 2 elements with the same value and that value is the maximum, output the minimal index.↵
Examples: Initial array = [5, 4, 3, 9]. Do first query $2, 3, 3$. array = [5, 4, 3, 3]. Do second query(0, 3). Answer = 0. Do first query $0, 1, 100$. array = [100, 100, 3, 3]. Do first query $3, 3, 1000$. array = [100, 100, 3, 1000]. Do second query(0, 1). Answer = 0.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Qualified 2020-10-11 15:19:51 0 (published)
en2 English Qualified 2020-10-11 15:19:38 131 (saved to drafts)
en1 English Qualified 2020-10-11 04:26:42 617 Initial revision (published)