Всем привет.
Можете ли вы подсказать как написать дерево отрезков с запросами видов:
l r x умножить все числа в отрезке с l по r на х
l r x прибавить ко всем числам в отрезке с l по r х
? р вывести элемент на позиции р
Заранее спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Всем привет.
Можете ли вы подсказать как написать дерево отрезков с запросами видов:
l r x умножить все числа в отрезке с l по r на х
l r x прибавить ко всем числам в отрезке с l по r х
? р вывести элемент на позиции р
Заранее спасибо.
Название |
---|
Дерево отрозков: обновление на отрезке
Спасибо, кэп. К счастью я знаю о существование этого сайта. Хотелось бы узнать как одновременно умножать и плюсовать с помощью проталкивание!!!
Ну тогда почитай, там хорошие объяснения
Можно и без проталкивания. В каждой вершине будем хранить toAdd, toMult. Когда проходим вершину будем ответ умножать на toMult/добавлять toAdd. Будем ходить снизу вверх.
Имеешь ввиду запускать update с каждого листа???
Нет, делать Update с верху, но выводить ответ снизу.
не понял
Два push(), для умножения и для прибавления! А можно ссылку на задачу?
А как узнать что делать раньше, умножение или прибавление?
Республиканская-2013(Казахстан) задача F.
Модификация должна хранится в виде двух чисел: mul — на что умножить число, и add — что к нему прибавить. Если нужно в "модификацию" добавить умножение на x, то
mul *= x, add *= x
, если добавить x тоadd += x
; И дерево отрезков с проталкиванием.Понятно,спасибо.