木DPに帰着するところまでは、公式解説 と同じです。

公式解説と同様、次の要件を満たすデータ構造があればこの問題を解くことができます。

• (多重)集合 \(S\) に \(X\) を追加する。
• \(S\) から \(X\) を削除する。
• \(S\) の中央値を求める。

これらのクエリは、Binary Trie というデータ構造を使うことで効率的に処理することができます。

簡潔に述べると、Binary Trie は、整数を 2 進表記で管理する Trie 木です。(詳細は各自で調べてください。)
集合を管理するデータ構造としては多機能な上に、平衡二分木などに比べて実装が軽いのが特徴です。

Binary Trie を使うと、次のようなクエリを \(O(\log \max X)\) で処理することができます。

• (多重)集合 \(S\) に \(X\) を追加する。
• \(S\) から \(X\) を削除する。
• \(S\) の中で \(k\) 番目に小さい値を求める。( \(k\) の値はクエリごとに異なってもよい)

今回の場合は \(S\) の中央値が必要ですが、それは \(3\) 番目のクエリを高々 \(2\) 回呼び出すことで計算できます。