Выпуклая оптимизация корпуса Java
Недавно я прочитал статью из PEG Wiki о трюке с выпуклым корпусом. Удивительно, но в конце статьи я прочитал, что мы можем достичь полностью динамического варианта трюка (что означает отсутствие условий применимости), если мы будем хранить строки в std::set. Хотя я понял упомянутый подход, я всегда терплю неудачу, когда пытаюсь его реализовать.
Другими словами, существует массив A размера n, где каждый элемент массива содержит два натуральных числа ai и bi.
Есть Q запросов, где каждый запрос может быть одного из двух типов:
1) Учитывая положительное целое число х, найти max (aix + bi) для всех я от 1 до п
2) Обновите значения ai и bi для некоторых i.
Значение для обновления будет в неубывающем порядке, т.е. ai1>=ai2 and bi1>=bi2 for Q >= i1 > i2 >= 1,
Обновить часть можно с помощью удаления предыдущей строки и добавления новой строки. Я ищу обновление и запрос части для амортизируемой сложности (log n) в Java