Qualified's blog

RMQ with lazy updates
By Qualified, history, 4 years ago, In English

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.

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Lol why do you keep asking for data structures?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    They are cool, duh! Tbf my man just needs to learn lazy segtree better and do more problems and that would answer half is questions though.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I need to use it in different problems. 272C - Dima and Staircase is the problem that I am working on rn.

    → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Just use Segment Tree

https://ideone.com/M1l9vm

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).

→ Reply