各 \(i\) ごとに \(A_i, \dots, A_{i+M-1}\) を実際にソートしていては、実行時間制限に間に合いません。そこで、\(i\) を \(1\) 増やしても、\(A_i, \dots, A_{i+M-1}\) を昇順にソートしたときの先頭 \(K\) 項はさほど変わらないことに注目してみます。
\(A_i, \dots, A_{i+M-1}\) のうち小さい方から \(K\) 個の値からなる多重集合を \(L\)、それ以外の値からなる多重集合を \(R\) とおきます。答えは \(L\) に属する値の総和なので、\(i\) を \(1\) 増やしたときに高速に \(L, R\) を更新することができればよいです。

\(L, R\) の定義は次の条件が全て成り立つことと同値です :

• \(|L| = K\)
• \(L \cup R = \{A_i, \dots, A_{i+M-1}\}\)
• \(\max L \leq \min R\)

\(i\) を \(1\) 増やしたとき、\(A_i\) が取り除かれ、\(A_{i+M}\) が追加されます。一旦 \(|L| = K\) の条件を忘れて、他の二つが保たれるように処理を行うと、

• \(A_i\) が \(L, R\) のどちらに属するか判定し、その集合から \(A_i\) を取り除く。
• \(A_{i+M} \lt \max L\) なら \(L\) に、そうでないなら \(R\) に \(A_{i+M}\) を追加する。

となります。これらの処理の後、\(|L| = K\) は保証されませんが、\(K - 1 \leq |L| \leq K+1\) が成り立っているので、\(L\) から \(R\)、\(R\) から \(L\) に高々 \(1\) 個の要素を移動することにより \(|L| = K\) を成り立たせることができます。

以上の操作は、順序集合を管理することのできるデータ構造を用いて各 \(O(\log N)\) で実現できます。\(i = 1\) の場合の \(L, R\) を求めたあと、順番に \(i\) の値を増やしていくことにより、元の問題を \(O(N \log N)\) で解くことができました。