Anzahl der Vertauschungen durch Heapify
Angenommen, Sie beginnen mit einem leeren Heap. Nun sollen Sie
q Anfragen (Queries) durchführen. Dabei gibt es zwei Arten von Anfragen:add x– fügtxdem Heap hinzu
pop– entfernt die Wurzel (root) des Heaps
Für jede dieser Anfragen soll ausgegeben werden, wie viele Vertauschungen (Swaps) nötig sind, um den Heap so anzupassen, dass er wieder die Max-Heap-Eigenschaft erfüllt.
Bei
pop-Operationen zählt sowohl das Vertauschen der Wurzel mit dem letzten Element als auch jede weitere Vertauschung, die notwendig wird.Eingabe
Die erste Zeile der Eingabe enthält die ganze Zahl
q (1 ≤ q ≤ ).Die nächsten
q Zeilen enthalten die Anfragen – jede Anfrage steht dabei in einer separaten Zeile. Es ist garantiert, dass bei allen add-Anfragen der Wert von x betragsmäßig nicht größer als ist.Ausgabe
Die Ausgabe besteht darin, für jede Anfrage separat die Anzahl der durchgeführten Vertauschungen auszugeben (jeweils in einer eigenen Zeile).
Beispiele
Eingabe | Ausgabe |
7
add 1
add 2
add -3
add 4
pop
add -2
pop | 0
1
0
2
2
0
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB