Автокомментарий: текст был обновлен пользователем jk_qq (предыдущая версия, новая версия, сравнить).

Sorry, криво прочитал условие.

Я не знаю другого способа это сделать, кроме как корневой декомпозицией. Разобьём массив на кусочки длины k. Будем в каждом кусочке держать сами числа, верхнюю грань выпуклой оболочки точек (i, x_i) и пару чисел k, b — коэффициенты арифметической прогрессии ki + b, которую надо прибавить на этом кусочке.

Нетрудно видеть, что max(x_i + ki + b) = b + max(x_i + ki), под максимумом стоит скалярное произведение (x_i, i) на вектор (1, k), значит мы ищем самую удалённую в некотором направлении точку из нашего множества, а такая точка всегда лежит на выпуклой оболочке. Значит, точку максимума можно найти бинарным поиском по выпуклой оболочке.

Таким образом, применяя операцию изменения, мы должны просто изменить коэффициенты k и b во всех кусочках, которые попали в запрос целиком, а на не более, чем двух кусочках, которые мы затронули частично, просто целиком перестроить всю структуру. Соответственно, чтобы спросить максимум на отрезке, его нужно поискать в кусочках, которые попали целиком, бинарным поиском, и в не более, чем двух кусочках, просто проитерировавшись по всему блоку.

Время работы получается на изменение, и на запрос. Таким образом, можно взят , и получить что-то, работающее за разумное время.

Не уверен, что это делается за .

Может кто оффлайн умеет решать, тоже было бы интересно услышать.

Помню, KADR как-то давно писал. Я тогда прочитал, проникся, поверил. Но, честно говоря, это не то, что хочется писать на контесте.