Educational Codeforces Round 87 D – Multiset を解いた記録
二分探索付き Fenwick Tree の動作チェックも兼ねて解いた問題
問題の概要
\(n\)個の整数からなる多重集合がある．\(q\)個のクエリを処理せよ．クエリの内容は以下の通り．
- 整数\(k\)を多重集合に追加する
- \(k\)番目に小さい数※を探し出し，削除する
※多重集合に属する全要素を昇順に並べ替えたときの\(k\)番目の要素．例えば \(\{1, 1, 2, 3, 5\}\) で「3番目に小さい数」は2である．
制約
- \(1 \leq n, q \leq 10^6\)
- \(1 \leq a_{i} \leq n-1\)
- 多重集合に属する整数は\(1\)以上\(n\)以下
- 削除クエリが飛んでくるとき，「\(k\)番目に小さい数」は必ず存在する
- 入力はすべて整数
解法
二分探索付き Fenwick Tree(Binary Indexed Tree) があればやるだけです．配列の\(i\)番目の要素に「\(i\)が何個あるか？」の情報を持たせます．
- \(k\)を追加：ft.add(k, 1)
- \(k\)を削除：ft.add(k, -1)
- \(k\)番目の要素を探す：ft.sum(x) >= k となるような最小のxを二分探索で探す
実装例
実行時間制限がキツイので，cin/coutを使う場合に入出力を高速化する呪文を使いました．