Maximale Teilarraysumme
Sie haben ein Array aus
n Ganzzahlen und q Abfragen (Queries). Es gibt zwei Arten von Abfragen: Entweder wird das Array an einem bestimmten Index p aktualisiert, oder es wird die maximale Teilarraysumme in einem Abschnitt [l; r] berechnet.Das sogenannte Maximum Sum Subarray innerhalb eines Abschnitts
[l; r] ist das zusammenhängende Teilarray, dessen Summe aller Elemente maximal ist. Anders ausgedrückt, Sie suchen die Summe eines Teilarrays [l'; r'], welches unter allen möglichen nicht-leeren Teilarrays im Bereich [l; r] die größte Summe aufweist.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ).Die folgenden
q Zeilen enthalten sämtliche Abfragen in der Form 1 l r (1 ≤ l ≤ r ≤ n) oder 2 p x (1 ≤ p ≤ n, ≤ x ≤ ). Diese beiden Arten von Abfragen haben folgende Bedeutung:- Bestimme die maximale Teilarraysumme im Abschnitt
[l; r].
- Aktualisiere den Wert im Array an Position
pmit dem Wertx.
Ausgabe
Für jede Abfrage vom Typ 1 soll das Programm die entsprechende Antwort ausgeben.
Beispiele
Eingabe | Ausgabe |
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