Minimale Zahl und Häufigkeit
Sie haben ein Array mit
n positiven ganzen Zahlen sowie q Abfragen. Jede Abfrage soll das Minimum in einem bestimmten Teilarray und die Anzahl der Vorkommen dieses Minimalwerts innerhalb dieses Teilarrays liefern. Schreiben Sie ein Programm, das diese Anfragen effizient verarbeitet.Eingabe
Die erste Zeile enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000), getrennt durch ein Leerzeichen. Diese geben die Größe des Arrays bzw. die Anzahl der Anfragen an.Die nächste Zeile enthält
n Zahlen (), getrennt durch Leerzeichen, die die Elemente des Arrays darstellen. Die folgenden q Zeilen beschreiben die einzelnen Abfragen. Jede Abfrage besteht aus zwei ganzen Zahlen l und r, getrennt durch ein Leerzeichen. Sie geben die linke und rechte Grenze des Teilarrays an.Ausgabe
Für jede Abfrage sollen Sie zwei ganze Zahlen ausgeben, getrennt durch ein Leerzeichen: Zuerst das Minimum im Teilarray und dann die Anzahl der Vorkommen dieses Minimalwerts im Teilarray.
Beispiele
Eingabe | Ausgabe |
5 3
3 2 5 2 1
1 3
2 4
1 5 | 2 1
2 2
1 1 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 3 MB