Всем привет!
Столкнулся с задачей прибавления на отрезке и запроса минимума и суммы. Как вы уже догадались запутался с пушами)
Подскажите какой инвариант вы поддерживаете и если можно скиньте код вашего ДО. Интересует рекурсивная реализация)
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:45:17
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:45:17
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 19:49:44 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been translated by jaguar1996 (original revision, translated revision, compare)
In every node of the segment tree put two values: sum of range and minimum of range.
Everytime you update a node with sum s and minimum x, update these values. If the range is [l, r], then s = s + (r - l + 1)·v (where v is the value you are adding to the range). Minimum should be updated too: x = x + v
Propagate the v value to the children as always.
hello,i have a stupid question about segment tree lazy propagation..why we need to Propagate the v ((where v is the value you are adding to the range)value to its children when we do a update function, can not we Propagate the v value to the children when we do query function(or say it just do what we really want to do?) can you explain it more details,becasue it confused me sevearl days to think this question...thanks in advance...
When applying lazy propagation, every node on the segment tree has some "lazy" values. In this case, the lazy values is the sum we are adding to a range.
If you update a node that represents a range [l, r], you must update the lazy values of its children, but nothing more, there's no need to go down to the leaves of the tree. We use these lazy values to update the nodes when needed.
So, when we attend another query, if we go to a node whose lazy value is on (it needs to be updated), we update the node and push the lazy value to the children (unless the node is a leaf)
This way, the complexity of the queries will be O(logn)
Было-бы приятно, если-бы тут была ссылочка на задачку.
Три задачи из тренировок СПбГУ на поиск минимума/максимума на отрезке, больше не встречал
Задача B
Задача C
Задача B
Here's mine. It is only addition and minimum, but can be easily edited to support sum operation.
You can watch this video: https://www.youtube.com/watch?v=Tr-xEGoByFQ
I code a segment tree and talk about how lazy propagation works. I don't remember if I talk about sum, but it is not very complicated if you can get a good understanding of lazy propagation.
This problem is kind of similar. You can see the editorial and others code to.
This problem is kind of similar. You can see the editorial and others code too.