Задачи
Можете ли Вы ответить на эти вопросы - 3
Можете ли Вы ответить на эти вопросы - 3
Задана последовательность целых чисел a_1, a_2, ..., a_n (|a_i| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций:
модифицировать i-ый элемент последовательности
для заданных x и y вывести MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}
Входные данные
Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a_1, a_2, ..., a_n. Третья строка содержит число m. Следующие m строк содержат запросы вида:
0 x y: изменить a_x на y (|y| ≤ 10000).
1 x y: вывести MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}
Выходные данные
Для каждого запроса вывести ответ как требуется в задаче.
Пример
Входные данные #1
4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3
Выходные данные #1
6 4 -3