No.043 C

$A$ が $[1,2,3,\dots,N]$ となるように変換する. そうすると, $B$ の転倒数が $A$ と $B$ の転倒距離となる.

そしてこの転倒数は隣接互換の積の数である. よって, この隣接互換の積を半分に分けて前半のみを $A$ にかけていけば $N$ は $A$ からも $B$ からも等しい転倒距離にある順列となる. 当然ながら $B$ の転倒数が奇数であれば $N$ は存在しない.

$B$ の転倒数の計算には Binary Indexed Tree を使う. $B$ を最初から見ていき, $b_i$ のインデックスの値をインクリメントする. そして区間 $[1, b_i)$ の合計を転倒数に足していく.

$A$ から $B$ の転倒数の半分の隣接互換をかけるのも Binary Indexed Tree を使う. 最初にすべてのインデックスの値を1としておく. そして $B$ を最初から見ていき, $b_i$ のインデックスの値をデクリメントする. $b_i$ を残りの中で一番左にもっていくのに必要な互換の積の数は区間 $[1, b_i)$ の合計であるので, 残りの転倒数がこれよりも大きければ $b_i$ を左に持っていき, 残りの転倒数から $b_i$ を左にもっていくのに必要な互換の積の数を引く. 残りの転倒数がこれよりも小さければ, $b_i$ を残りの転倒数の数だけ左に移動させる.