Subarray de Soma Máxima
Você tem um array de
n inteiros e q consultas. Existem dois tipos de consultas: atualizar o array em um índice p e calcular o subarray de soma máxima dentro de um subarray [l; r].O subarray de soma máxima dentro de um subarray
[l; r] é definido como um subarray contíguo que apresenta a maior soma de seus elementos. Em outras palavras, você precisa encontrar a soma do subarray [l'; r'] cuja soma de elementos seja a máxima entre todas as possibilidades de subarray não vazio dentro do intervalo [l; r].Entrada
A primeira linha da entrada contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000).A linha seguinte contém
n inteiros separados por espaço ( ≤ ≤ ).As próximas
q linhas contêm todas as consultas - 1 l r (1 ≤ l ≤ r ≤ n) ou 2 p x (1 ≤ p ≤ n, ≤ x ≤ ), representando os dois tipos de consultas:- Obter o subarray de soma máxima dentro do subarray
[l; r].
- Atualizar o array na posição
pcom o valorx.
Saída
Para cada consulta do tipo 1, o programa deve imprimir a resposta correspondente.
Exemplos
Entrada | Saída |
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