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:

  1. Obter o subarray de soma máxima dentro do subarray [l; r].

  2. Atualizar o array na posição p com o valor x.

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

To check your solution you need to sign in
Sign in to continue