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

Автор Qualified, история, 4 года назад, По-английски

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.

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

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

Lol why do you keep asking for data structures?

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

Just use Segment Tree

https://ideone.com/M1l9vm

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

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