RMQ with lazy updates

Revision en3, by Qualified, 2020-10-11 15:19:51

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)