Consultas de Subarray Máximo

#181

Made by: Crazynds

100MB

0.104s

Dado um array $A$ de $N$ inteiros, responda $Q$ operações do tipo:

1 i v: atualize $A[i] = v$.
2 l r: consulte a maior soma de subarray contíguo dentro de $A[l..r]$ (o subarray deve ter pelo menos 1 elemento).

Input

A primeira linha contém dois inteiros $N$ e $Q$ $(1 \le N \le 10^5,\ 1 \le Q \le 10^5)$.

A segunda linha contém $N$ inteiros $A_i$ $(-10^9 \le A_i \le 10^9)$.

As próximas $Q$ linhas contêm cada uma uma operação no formato descrito acima.

$(1 \le i \le N,\ -10^9 \le v \le 10^9,\ 1 \le l \le r \le N)$

Output

Para cada operação do tipo 2, imprima a resposta em uma linha separada.

Input Example

Output Example

6 3
-2 1 -3 4 -1 2
2 1 6
1 3 5
2 1 6

5
11

Explanation 1:
- **`2 1 6`** inicial: subarray $[4,-1,2]=5$. Resposta: $5$. - **`1 3 5`**: array vira $[-2, 1, 5, 4, -1, 2]$. - **`2 1 6`**: subarray $[1, 5, 4, -1, 2]=11$ ou $[5,4,-1,2]=10$... $1+5+4-1+2=11$. Resposta: $11$.

28 20
-9080 5357 9602 -1926 7275 1742 -2212 5106 -9560 3714 4521 1176 -1792 -9100 3316 -9438 271 1991 -6503 400 -7324 -860 2439 5747 -5897 3926 -4428 5605
1 6 -7875
1 13 9064
2 25 28
1 11 -7707
1 4 -9167
2 19 21
2 18 19
1 27 3018
2 28 28
1 8 -2645
2 19 23
2 8 19
2 12 21
2 10 10
1 21 7559
2 14 24
1 25 -4801
1 20 1662
1 16 -4794
2 28 28