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.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/10/2024 10:02:15 (i2).
Desktop version, switch to mobile version.
Supported by
Lol why do you keep asking for data structures?
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.I need to use it in different problems. 272C - Dima and Staircase is the problem that I am working on rn.
Just use Segment Tree
https://ideone.com/M1l9vm
Thanks! Really needed this.
What would the implementation be if we wanted to have range updates instead of point update? Lazy propagation? IDK.
Without lazy propagation it is possible to to point update and range query, or, range update and point query. With lazy propagation you can do both types of queries and updates.
Do you know the implementation with lazy propagation?
This is the one I use: https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LazySegmentTree.h.
The query part returns the element that is the largest in the interval [l, r — 1]. But is there a way for it to return the index of the element with the maximal value in the interval [l, r]?
You can modify the seg tree to use pairs instead of ints, and have the pairs contain {value, index}. Then modify the operation to return {max_value, index of max_value}.
Implementation? Nvm, I just solved the problem.
https://ideone.com/Fa5oy1
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).