順列の各要素に \(L\) or \(R\) のタイプを割り当てることにします． その後，\(R\) の要素を \(+N\) した上で求めた転倒数が swap 回数になります．

まず以下の命題を証明しておきます．

• 最適解において「\(i<j\), \(P_i>P_j\), \(P_i\) がタイプ \(R\), \(P_j\) がタイプ \(L\)」を同時に満たすような \((i,j)\) は存在しない．

背理法によって証明します． 今，ある最適解に対し，「\(i<j\), \(P_i>P_j\), \(P_i\) がタイプ \(R\), \(P_j\) がタイプ \(L\)」を同時に満たすような \((i,j)\) が存在するとします．ここで，\(j-i\) が最大になるペア \((i,j)\) を取ります． すると，\(P_i\) をタイプ \(L\), \(P_j\) をタイプ \(R\) にすることで転倒数を \(1\) 以上減らすことができます （細かい計算は場合分けで計算するだけなので省略）． これはもともとの解の最適性に矛盾します． よって示されました．

各組 \((i,j)\) (\(1 \leq i < j \leq N\)) に対し，\(P_i,P_j\) のタイプによって最終的な転倒数にどれだけ寄与するかを考えます． これをまとめたのが以下の図です．

 P_i < P_j        P_i > P_j
 i\j| L | R |     i\j| L | R |
 L  | 0 | 0 |     L  | 1 | 0 |
 R  | 1 | 0 |     R  | 1 | 1 |

ところで，先程示した命題により，\(P_i>P_j\) で \(i,j\) がタイプ \(R,L\) になるケースは最適解では登場しません． つまり，このケースのコストを増加させても最適解は変化しません． 天下り的ですが，このケースのコストを \(3\) にします．

 P_i < P_j        P_i > P_j           i<j              i<j, P_i > P_j
 i\j| L | R |     i\j| L | R |        i\j| L | R |       | L | R | 
 L  | 0 | 0 |     L  | 1 | 0 |   ->   L  | 0 | 0 |  +  i | 0 | 1 |
 R  | 1 | 0 |     R  | 3 | 1 |        R  | 1 | 0 |     j | 1 | 0 |

するとこのコストは最小カットで表現できるようになります． 具体的には，元問題は以下の手順で得られるグラフの最小 \(S-T\) カットを求めることに帰着されます．

• 超頂点 \(S,T\) 及び頂点 \(1,2,\cdots,N\) を用意する．
• 各ペア \((i,j)\) (\(1 \leq i < j \leq N\)) について，\(j \to i\) に容量 \(1\) の辺を追加する．
• 各ペア \((i,j)\) (\(1 \leq i < j \leq N\), \(P_i > P_j\)) について，\(S \to i\) と \(j \to T\) に容量 \(1\) の辺を追加する．

各頂点 \(1 \leq i \leq N\) について，\(S \to i\) 辺の容量を \(X_i\)，\(i \to T\) 辺の容量を \(Y_i\) とおきます．\(X_i,Y_i\) は簡単にわかります． 次にこのグラフの最小カット\(=\)最大流の容量を求めます．

各頂点 \(1 \leq i \leq N\) について，その influx \(f_i\) を \((i\) に流れ込むフロー \()-(i\) から流れ出るフロー \()\) と定義します． 正しい \(S-T\) フローでは \(f_i=0\) を満たす必要がありますが，この制約を外して各辺に適当なフローを流すことを考えます．

まず，すべての \(i\) について \(S \to i\) 辺と \(i \to T\) 辺に容量最大までフローを流します． その後で \(j \to i\) 辺 (\(i < j\)) の使い方を考えます． \(j \to i\) 辺を使うことは，\(f_i\) を \(1\) 増加させ，\(f_j\) を \(1\) 減少させることに対応します．

使う \(j \to i\) 辺を決めたあと，今持っているフローを正しい \(S-T\) フローに直してから最大流の流量を求める必要がありますが，実はこれは簡単です． 各頂点 \(i\) に対し，\(f_i>0\) を満たすならば \(i \to S\) に \(f_i\) だけ押し戻し，\(f_i<0\) ならば \(T \to i\) に \(|f_i|\) だけ押し戻せば良いです． ここで，\(f_i>X_i\) や \(|f_i|>Y_i\) のときの対処が難しいように見えますが，実はこのようなケースは考慮する必要がありません． 最初に \(X_i,Y_i\) にそれぞれ \(10^{100}\) を加算したと考えればよいです．

結局，\(\sum_{1 \leq i \leq N} |f_i|\) を最小化することが目標になりました．

これは以下のような貪欲で解くことができます．

• 各 \(j=1,2,\cdots,N\) について以下の操作を行う．
  • (現在の) \(f_1,\cdots,f_{j-1}\) を昇順に並べたものを \(g_1,\cdots,g_{j-1}\) とする．各 \(1 \leq i < j\) について，\(g_i+1\leq f_j-i\) ならば \(j \to i\) 辺を使う．

貪欲の正当性の証明: 任意のタイミングにおいて，\(y-x \geq 2\) のとき，\((x,y) \to (x+1,y-1)\) とできるならしてもよい．これは後ろから帰納法を回すとわかる．\((x,y) \to (x+1,y-1)\) を可能な限りやるという操作が上で説明した貪欲に一致する．

あとはこの貪欲を高速に実行できれば良いです． 最も考察が簡単な代わりに実装が難しい方法は，平衡二分探索木を使うことです． ですが実は Fenwick Tree だけで実装できます． 各 \(v\) (\(-N \leq v \leq N\)) について，\(f_i=v\) を満たす \(i\) の個数 \(c_i\) を管理することにします．

最も難しいクエリは「\(k\) が与えられるので，すべての \(i<k\) について \(c_{i+1} := c_i\) と変更せよ」というものです．

これを高速に処理するために数列 \(a,b\) を用意します． 一言で言えば，\(a\) は active な index を管理するテーブルです． より正確に述べます．\(a\) の要素は \(0\) か \(1\) です．そして \(a\) の中で \(i\) 番目に \(1\) がある位置を \(x\) とすると，\(b_x\) に \(c_i\) の値が保存されるようにします． こうすれば，先程述べた最も難しいクエリは，\(a\) の要素を \(1\) つ \(0\) に変えるだけで処理できます． なお，\(i\) が負の場合もありますが，これは適切な offset を足してやることで解決します．

\(a,b\)，そして更に \(a_i+b_i\) の値を Fenwick Tree で管理してやることで，貪欲で必要なすべての操作が \(O(\log N)\) 時間で処理できるようになります． よってこの問題は全体で \(O(N \log N)\) 時間で解けます．

回答例