0-basedで考える。列(Si)を[0,m),[m,N)に分けた時に、左右の和を等しくするようなスワップが何個あるか数える。まず、右の和のほうが大きいことが有効なスワップが存在する必要条件である。右の和が左の和よりD(m)だけ大きいとする。このとき、D(m)が偶数なら左の区間のSiと右の区間のSi+D(m)/2を交換すると和が等しくなる。添え字iが有効である条件は0≤i<m,m≤i+D(m)/2<Nで、これはmax(0,m−D(m)/2)≤i<min(m,N−D(m)/2)とまとまる。この区間の長さが有効なスワップの数に等しいので、すべてのmについて足せばよい。ただしD(m)=0の場合は区間をまたいで数を移動する必要がないので特別扱いして、左の区間内と右の区間内のスワップの総数を数える。
さて、0≤D(m)<2Nが必要なことを考えると、有効なmは多くないはずだ。mが増加するとき、D(m)が正から負に変わる地点を考えると、この地点は全体の半分よりは右にあるはずだから、その付近ではmが1動くごとにおおむね2⋅N/2=N程度はD(m)が変化することになる。したがって、高々3つ程度のmについて数えれば十分という見積もりができる。実装の際はD(m)≥0であるような最大のmを二分探索などで求めておいて、そこから下っていけばよい。
