Subarreglo de Suma Máxima
Se te proporciona un arreglo de
n enteros y q consultas. Existen dos tipos de consultas: actualizar el arreglo en un índice p y calcular el subarreglo de suma máxima dentro de un subarreglo [l; r].El subarreglo de suma máxima dentro de
[l; r] se define como el subarreglo contiguo que tenga la mayor suma de sus elementos. En otras palabras, se debe hallar la suma del subarreglo [l'; r'] cuyo total sea máximo entre todos los subarreglos no vacíos dentro del rango [l; r].Entrada
La primera línea de la entrada contiene dos enteros
n y q (1 ≤ n, q ≤ 100 000).La siguiente línea contiene
n enteros separados por espacio: ( ≤ ≤ ).A continuación, se dan
q líneas que representan todas las consultas, las cuales pueden ser de la forma 1 l r (1 ≤ l ≤ r ≤ n) o 2 p x (1 ≤ p ≤ n, ≤ ≤ ), indicando los dos tipos de consultas:- Obtener el subarreglo de suma máxima dentro del subarreglo
[l; r].
- Actualizar la posición
pdel arreglo con el valorx.
Salida
Para cada consulta de tipo 1, el programa debe imprimir la respuesta correspondiente a dicha consulta.
Ejemplos
Entrada | Salida |
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