e-olymp
Задачи

Можете ли Вы ответить на эти вопросы - 3

Можете ли Вы ответить на эти вопросы - 3

Задана последовательность целых чисел a1, a2, ..., an (|ai| ≤ 10000 , 1 ≤ n50000). Над ней Вам следует выполнить m (m50000) операций:

  • модифицировать i-ый элемент последовательности
  • для заданных xиy вывести MAX {ai + ai+1 + ... + aj, xijy}

Входные данные

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a1, a2, ..., an. Третья строка содержит число m. Следующие m строк содержат запросы вида:

  • 0 x y: изменить ax на y (|y| ≤ 10000).
  • 1 x y: вывести MAX {ai + ai+1 + ... + aj, xijy}

Выходные данные

Для каждого запроса вывести ответ как требуется в задаче.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
Выходные данные
6
4
-3