ヒント集 → https://atcoder.jp/contests/arc210/editorial/14522

[1] 残る要素とは

\(N=2K\) とします．\(N+M\) 個の数 \(A_1, A_2, \ldots, A_N, B_1, B_2, \ldots, B_M\) をソートしたものを，\(x_1, x_2, \ldots, x_{N+M}\) とします．これらには値の重複がありえますが，適当な方法で順序をつけておき，中央値削除もその順序にしたがって行うこととします．

このとき，最後に残る要素は \(x_1, x_2, \ldots, x_K\) および \(x_{N+M-K+1}, x_{N+M-K+2},\ldots,x_{N+M}\) の \(N\) 個（つまり小さい方から \(K\) 個，および大きい方から \(K\) 個）であることが証明できます．

実際，削除操作の対象となる要素は，「その要素より小さい要素が \(K\) 個以上存在する」「その要素より大きい要素が \(K\) 個以上存在する」の両方を満たすもの以外にありえません．よって小さい方から \(K\) 個，大きい方から \(K\) 個の要素は削除対象となりえません．

最終的に残る要素は \(N=2K\) 個なので，最後に残る要素はこれらで全てということになります．

[2] 答の計算

結局，本問を解くには次のことができればよいことになります．

• \(N+M\) 個の要素からなる多重集合 \(S\) が与えられる．
• \(S\) に対して \(1\) 要素を削除し，新たに \(1\) 要素を追加するというクエリが \(Q\) 回来る．クエリのたびに，\(S\) の小さい方から \(K\) 個の総和，および大きい方から \(K\) 個の総和を求める．

これはデータ構造の基本的な問題で，さまざまな解法が考えられます．

\(O((N+M+Q)\log (N+M+Q))\) 時間程度で解ける比較的高速な方法をいくつか挙げると，

• 区間和を求める機能を持たせた平衡二分木を使う．
• 値の大きさをインデックスとした列を考えて，Fenwick 木やセグメント木を使う．
• \(S\) を昇順で \(K\) 個，\(N+M-2K\) 個，\(K\) 個に分割して \(S_1, S_2, S_3\) として，これらを管理する（multiset や priority queue を使う）．

などの方針が考えられます．

• 解答例（Fenwick 木の利用）https://atcoder.jp/contests/arc210/submissions/70836409
• 解答例（優先度付きキューの利用）https://atcoder.jp/contests/arc210/submissions/70836694