Please help with this problem from October circuit from Hackerearth. In their editorial they just posted solution code. Please provide some idea(I know that Segment tree can be used) but I am not sure how to handle the reverse operation.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 159 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 150 |
| 6 | atcoder_official | 148 |
| 6 | SecondThread | 148 |
| 8 | nor | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.07.2024 00:23:03 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
This Problem helped me in solving this problem — GSS1
Disclaimer: There may be multiple ways to solve this problem. Below I outline my approach during the contest.
Assuming that you can do basic stuff with segment trees, I suggest reading up this article: Answering max subarray range queries
Try the problem on your own for some time after reading up the article. If you don't make much progress, read up the hints in the order till you get to something new which you didn't think of earlier.
Now coming to the reversing part, consider the 3 intervals (or 2 when either of the side ones converge to 0 length) I1: = [1, L - 1], I2: = [L, R] and I3: = [R + 1, N].
For each interval Ik denote by Prek, Sufk, Sumk, maxSubk the max prefix sum, max suffix sum, total sum and the max subarray sum respectively (for 1 ≤ k ≤ 3). ...
Note that reversing interval I2, only swaps the value of Pre2 and Suf2 for it. ...
Then the maximum subarray sum of the array (after I2 has been reversed) will be the maximum of the following 6 possible sums:
maxSub1
maxSub2
maxSub3
max(0, Suf1) + Sum2 + max(0, Pre3)
max(0, Suf1) + max prefix sum of reversed I2 = max(0, Suf1) + Suf2
max suffix sum of reversed I2 + max(0, Pre3) = Pre2 + max(0, Pre3) ...