yukicoder No.649 ここでちょっとQK！

• 問題

問題概要

自然数K,Qが与えられる.以下のクエリQ個を処理せよ.
1. 配列に値Xを挿入する
2. 配列のK番目に大きい値を出力し,削除する
1 <= Q,K <= 2*10⁵, 1 <= X <= 10¹⁸

解法

想定解で解いた.
minキューとmaxキューを用意し,maxキューにはK番目に小さい値までを入れ,minキューにはそれ以降の値を入れる.
解説と同じように場合分けして処理を書いてけば良い.

Kが固定ならこれで良いが,Kが毎回変わる場合には少し複雑になる.
ARC 033 C - データ構造がまさにこの問題.
この問題にはいくつか解がある. 1. 座標圧縮してFenwick Tree
クエリを先読みして現れる全ての数を座標圧縮すれば 1 <= v' <= Qとなる.以下はこの数に変換して使う.
蟻本にもあるが,これはソートして何番目の数かを二分探索すれば良い.O(QlogQ).
座標のサイズのFenwick Treeを作って以下のように処理すれば解ける.
クエリ1(v) treeのv'の要素に+1する
クエリ2(K) treeのv'未満の総和が初めてK-1以上になる(それ以下の値がK-1個ある)ようなv'を二分探索する
クエリ1がO(logQ), クエリ2がO((logQ)²)で解けるので全体でO(Q(logQ)²).

1. 平衡二分木を作る
   yukicoderの解説に書いてある. gnu拡張を使うと楽.
2. 平方分割
   ARC解説にあるけどわからん(そのうち)

メモ

K固定はできたが,Kが可変だと解けなかった気がする.汎用性が高い問題なので覚えておきたい.

コード