\([a_i, a_{i+K})\) の区間だけを整地することを考える. \(A_i = \{ a_i, \dots, a_{i+K} \}\) とする.

高さを \(x_i\) に揃えるとすると, コストは \(C_i = \sum \vert a_j-x_i \vert\) となり, これの最小値を求める問題となる. そしてこれは \(x_i\) が \(A_i\) の中央値のときであることが分かっている. (中央値が整数にならない (\(.5\) が含まれる) 場合はその数のどちら側の整数でもいい)

この \(x_i\) の求め方であるが, \(a_j\) を座標圧縮しておいてキーとして Fenwick Tree に \(+1\) ずつするように入れ, 二分探索で求めることができる. また, \(S_i\) も同様に Fenwick Tree に \(+a_i\) ずつするように入れておけばいい. こうすることで \(i\) を増やしたときにそれぞれの Fenwick Tree を操作することで \(x_{i+1}, S_{i+1}\) も高速に求めることができる.