Hints: https://atcoder.jp/contests/arc210/editorial/14585

[1] Which elements remain?

Let \(N=2K\). Let \(x_1, x_2, \ldots, x_{N+M}\) be the \(N+M\) numbers \(A_1, A_2, \ldots, A_N, B_1, B_2, \ldots, B_M\) sorted. These may have duplicate values; we order them in some way and perform median deletion according to that order.

Then, it can be proved that the elements remaining at the end are the \(N\) elements \(x_1, x_2, \ldots, x_K\) and \(x_{N+M-K+1}, x_{N+M-K+2},\ldots,x_{N+M}\) (that is, the smallest \(K\) elements and the largest \(K\) elements).

Indeed, an element can be a deletion target only if both “there are \(K\) or more elements smaller than it” and “there are \(K\) or more elements larger than it” hold. Therefore, the smallest \(K\) elements and the largest \(K\) elements cannot be deletion targets.

Since \(N=2K\) elements remain in the end, these are all the elements that remain at the end.

[2] Computing the answer

In conclusion, to solve this problem, we need to be able to do the following:

• We are given a multiset \(S\) consisting of \(N+M\) elements.
• We receive \(Q\) queries, each of which deletes one element from \(S\) and adds one new element. For each query, find the sum of the smallest \(K\) elements of \(S\) and the sum of the largest \(K\) elements of \(S\).

This is a basic data structure problem, and various solutions are possible.

Here are several relatively fast methods that can solve it in about \(O((N+M+Q)\log (N+M+Q))\) time:

• Use a balanced binary tree with the ability to find range sums.
• Consider a sequence indexed by value size and use a Fenwick tree or segment tree.
• Divide \(S\) into \(K\) elements, \(N+M-2K\) elements, \(K\) elements in ascending order as \(S_1, S_2, S_3\), and manage these (using multiset or priority queue).

and so on.

• Sample solution (using Fenwick tree) https://atcoder.jp/contests/arc210/submissions/70836409
• Sample solution (using priority queue) https://atcoder.jp/contests/arc210/submissions/70836694