Range Maximum Queries (Abfragen zum maximalen Wert in einem Bereich)
Du hast ein Array bestehend aus
n Elementen sowie q Anfragen (Queries). Es gibt zwei Arten von Anfragen:- Bestimme den Maximalwert in einem definierten Bereich.
- Aktualisiere einen Wert im Array an einer bestimmten Position.
Deine Aufgabe ist es, diese Anfragen effizient zu bearbeiten.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000). Diese geben die Anzahl der Elemente im Array und die Anzahl der Queries an.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (). Dies sind die Anfangswerte im Array.Die nächsten
q Zeilen beschreiben jeweils eine Anfrage:- Für Range-Maximum-Queries beginnt die Zeile mit einer
1, gefolgt von zwei ganzen Zahlen und (). Dieser Bereich[]gibt an, für welche Indizes der maximale Wert ermittelt werden soll.
- Für Array-Updates beginnt die Zeile mit einer
2, gefolgt von zwei ganzen Zahlen und (). Hierbei wird das Element an Position auf den neuen Wert gesetzt.
Ausgabe
Für jede Anfrage des Typs Range Maximum Query sollst du den maximalen Wert im angegebenen Bereich in einer neuen Zeile ausgeben.
Beispiele
Eingabe | Ausgabe |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 4
9
7 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB