Максимальная сумма подотрезка
Вам дан массив из
n целых чисел и q запросов. Существует два типа запросов: обновить массив в позиции p и вычислить максимальную сумму подотрезка в диапазоне [l; r].Под максимальной суммой подотрезка в
[l; r] подразумевается сумма элементов такого непрерывного подотрезка [l'; r'], при которой сумма элементов оказывается наибольшей из всех возможных непустых подотрезков в пределах [l; r].Входные данные
В первой строке заданы два числа
n и q (1 ≤ n, q ≤ 100 000).Во второй строке содержится
n целых чисел: (от -10^9 до 10^9).В следующих
q строках располагаются запросы одного из двух видов: 1 l r (1 ≤ l ≤ r ≤ n) или 2 p x (1 ≤ p ≤ n, от -10^9 до 10^9). Они означают:- Найти максимальную сумму подотрезка в диапазоне
[l; r].
- Обновить значение массива в позиции
pнаx.
Выходные данные
Для каждого запроса первого типа выведите результат — то есть максимально возможную сумму подотрезка в заданном диапазоне.
Примеры
Input | Входные данные |
8 4
-2 1 -3 4 -7 2 1 -5
1 2 6
2 5 0
1 2 6
1 1 2 | 4
6
1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB