Доброго времени суток!
Помогите решить такую задачу:
Есть M торговцев. Каждый торговец торгует начиная с города Li до Ri. Свой товар торговец начинает торговать с города Li за цену Xi, и с каждым городом цена товара увеличивается на 1 единицу, т.е В городе Li за Xi , в городе Li+1 за Xi+1, в городе Ri за Xi+ Ri — Li+1.
И для каждого города нужно определить максимальную цену товара за всю историю.
Советую просто научиться дереву отрезков. Нажми сюда
Если все стоимости нужно узнать только в конце, то дерево отрезков не нужно
Можно по подробнее ???
Назовем побочной ценой число pi - i, где pi — это цена товара в городе номер i. Теперь мы можем заменить заданные присвоения на присвоения некоторого числа на отрезке побочных цен.
Пусть теперь у нас есть запросы присвоить на отрезке [L, R] побочную цену y. Тогда создадим события начала этой побочной цены и конца. Отсортируем их и пробежимся сканлайном. Пробегаясь по отсортированным событиям, мы можем для каждого города посчитать максимальную побочную цену в нем: будем хранить стек с поддержкой максимума и при начале очередного отрезка будем класть y в стек, при его конце — удалять вершину стека. Теперь мы можем для каждого города посчитать максимальную побочную цену, прибавить к ней i и получить тем самым искомую.
Можно идти слева направо, поддерживая set активных торговцев, отсортированный по Xi - Li
Ой, нельзя:) я не о той задаче подумал.
А что не так?
Я думал надо посчитать сумму, а не максимум
А как вообще решается задача, это же не простая задача RMQ на отрезке.
В данном случае лучше построить дерево для b[i] = a[i] — i. Тогда мы имеем обычные присвоения на отрезке.
Оно? http://mirror.codeforces.com/blog/entry/6492#comment-153115
спасибо всем большое! Решил!!!