| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 162 |
| 3 | maomao90 | 159 |
| 3 | atcoder_official | 159 |
| 5 | cry | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
The problem is: Given an array of 10^5 numbers and 10^5 queries, each query is like "i j" means: find the largest possible value A[y]-A[x] such that i<=x<=y<=j.
The analysis of this problem said it is easy to do with segment tree, but I have no idea, can anyone please explain how? (btw, it also has update operation, otherwise I could do it with offline semgment tree)
Thanks in advance!
Link to the problem?
For a node in the segment tree keep :
<min,max,answer>. Now think about how you would merge two nodes.for each node keep:
pair<min,max>now the answer for each query is :
quermax-querminSpoiler