ABC 401-500/ABC458D - Chalkboard Median - 競技プログラミング用 知識集積所

---

問題

ABC458D

必要知識

B以下レベルの内容は省略

• 特になし

考え方

愚直にはvectorに毎回2つの値を付け足してソートすればよい。
しかしそれではTLEしてしまうので工夫する。

毎回ソートしなくても、見るのは所詮中央値付近だけである。
ということは、黒板にある数の個数が2k+1個だとして、

• 中央値より小さいk個を集めたもの（最も大きいものをいつでも取り出せる）
• 中央値そのもの
• 中央値より大きいk個を集めたもの（最も小さいものをいつでも取り出せる）

にわけてデータを持っておけば十分である。
（実際には中央値と同じ値が複数ある場合もあるが、その場合も個数で同様に管理する）

つまり、priority_queue※を2つと整数1つを持ち、クエリごとに

• 2つの値をそれぞれ、中央値と比較して適切な方のpriority_queue※に入れる
• priority_queue※間で個数に差がある場合、多い方のtop→中央値→少ない方と数を移行する

をすればよい。

解答例

解答例

注意点

別解