Min-Max-Bereichsabfrage
Du hast ein Array mit
n Elementen und q Anfragen. Es gibt zwei Arten von Anfragen:- Bestimme das Minimum und das Maximum innerhalb eines angegebenen Bereichs.
- Aktualisiere das Array an einer bestimmten Position.
Dein Ziel ist es, diese Anfragen effizient zu bearbeiten.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000). Diese stehen für die Anzahl der Elemente im Array und die Anzahl der Anfragen.Die zweite Zeile enthält
n durch Leerzeichen getrennte Zahlen (), die die anfänglichen Elemente des Arrays repräsentieren.Die nächsten
q Zeilen beschreiben jeweils eine Anfrage:- Bei Anfragen zum Minimum-Maximum-Paar für einen Bereich: Die Zeile beginnt mit der Zahl
1, gefolgt von zwei ganzen Zahlen und (). Diese geben den Indexbereich[]an, in dem das Minimum-Maximum-Paar ermittelt werden soll.
- Bei Anfragen zur Aktualisierung des Arrays: Die Zeile beginnt mit der Zahl
2, gefolgt von zwei ganzen Zahlen und (). Dabei wird das Element an Position durch den neuen Wert ersetzt.
Ausgabe
Für jede Anfrage zum Minimum-Maximum-Paar gib das kleinste und das größte Element innerhalb des angegebenen Bereichs in separaten Zeilen aus.
Beispiele
Eingabe | Ausgabe |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB