Всем привет.
Можете ли вы подсказать как написать дерево отрезков с запросами видов:
l r x умножить все числа в отрезке с l по r на х
l r x прибавить ко всем числам в отрезке с l по r х
? р вывести элемент на позиции р
Заранее спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Всем привет.
Можете ли вы подсказать как написать дерево отрезков с запросами видов:
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
; И дерево отрезков с проталкиванием.Понятно,спасибо.