解法

数列 \(A, B\) をまとめた \(1\) つの数列をソートする解法です。

昇順に走査しながら、次の情報を管理します。

• これまでに出現した
  
  • \(A\) の要素の個数 \(C_A\) と総和 \(S_A\)
  • \(B\) の要素の個数 \(C_B\) と総和 \(S_B\)
• 各要素が出現したときに、対応する寄与を答えに加算

対応する寄与は、 出現した要素が \(A_i\) のとき \(A_i C_B - S_B\) 、 出現した要素が \(B_j\) のとき \(B_j C_A - S_A\) です。

計算量はソートがボトルネックとなり、 \(O((N+M) \log(N+M))\) です

補足

\(A\) と \(B\) の要素の各ペア \((A_i, B_j)\) について、\(A_i\) が先にくる場合 \((A_i \leq B_j)\) の場合と \(B_j\) が先にくる場合 \((B_j \leq A_i)\) の場合を考えます。(イコールは寄与が \(0\) なので適当に処理してよいです)

\(A_i\) が先にくる場合、寄与は \(B_j - A_i\) です。同じ \(B_j\) についてまとめることで、\( \sum_k (B_j - A_{i_k}) =B_j C_A - S_A\) が得られます。

\(B_j\) が先にくる場合、同様にして、 \(A_i C_B - S_B\) が得られます。

実装例(C++)