No.649
\(K\) 番目以下の数値を保持する赤黒木1と \(K\) 番目以降の数値を保持する赤黒木2を用意する.
クエリ1がきたときは以下のように処理する.
- 赤黒木1のサイズが \(K\) 未満ならば赤黒木1に \(v\) を挿入する.
- 赤黒木1の最大値が \(v\) 未満ならば赤黒木2に \(v\) を挿入する.
- 赤黒木1の最大値を削除し, これを赤黒木2に挿入する. そして赤黒木1に \(v\) を挿入する.
クエリ2がきたときは以下のように処理する.
- 赤黒木1のサイズが \(K\) 未満ならば
-1
を出力する. - 赤黒木1の最大値を削除し, これを出力する. そして赤黒木1に赤黒木2の最小値を削除して挿入する.