Sottoarray a somma massima
Ti viene fornito un array di
n interi e q interrogazioni. Esistono due tipi di interrogazioni: aggiornare l’array in una posizione specifica p, oppure calcolare il sottoarray a somma massima all’interno di un sottoarray [l; r].Il sottoarray a somma massima all’interno di
[l; r] è definito come il sottoarray contiguo che ha la somma più alta dei propri elementi. In altre parole, devi trovare la somma del sottoarray [l'; r'] tale che la somma dei suoi elementi sia la più grande possibile tra tutti i sottoarray non vuoti compresi nell’intervallo [l; r].Input
La prima riga dell’input contiene due interi
n e q (1 ≤ n, q ≤ 100 000).La riga successiva contiene
n interi separati da spazio ( ≤ ≤ ).Le successive
q righe contengono tutte le interrogazioni: 1 l r (1 ≤ l ≤ r ≤ n) o 2 p x (1 ≤ p ≤ n, ≤ x ≤ ), che rappresentano i due tipi di operazioni:- Ottenere il sottoarray a somma massima in
[l; r].
- Aggiornare l’array in posizione
pcon il valorex.
Output
Per ogni interrogazione di tipo 1, il programma deve stampare la risposta corrispondente.
Esempi
Ingresso | Uscita |
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