ARC225 E - Gap Swap (hard)

考え方

以下、0-indexed で考える。

また、D問題でも使った文字列対応を考える。
すなわち、各数について、以下の文字を対応させる。

• ある数が本来そこより右にいるべき場合、'R'
• ある数が本来そこより左にいるべき場合、'L'
• 正しい位置にいる場合は 'N'

この文字列で、'N' 以外で最初に出現する文字は必ず 'R' である。
また、'N' 以外で最後に出現する文字は必ず 'L' である。
よって、'N' を無視した場合に 'R' の次に 'L' があるところが少なくとも $1$ ヶ所ある。
したがって、'R' の次に 'L' があるところを探して交換することは、完了状態以外では必ず可能である。

この交換を任意の順で続けることが最小手数になる証明のスケッチを示す。
（本気でやると手間なので、かなり荒い証明になっている）

まず、'R' の次に 'L' がある組のうち最も右にあるものを交換し続けることを考える。
この場合、最も右にある 'R' がまっすぐ目的地に入ることになる。
もし最も右にある 'R' より右にある 'L' が、移動 $1$ 回で目的地に移動できたとしよう。
これを先に目的地に送ると、一見手数が減りそうに見えるが、実はそんなことはない。
というのは、これは 'L' を揃えるのに $1$ 手使って 'R' の移動を $1$ 回減らすだけ。
手数も終状態も何も変わらないのである。

ということで、'R' の次に 'L' がある組のうち最も右のものを交換し続けるのは、最短手順の $1$ つ。
'R' の次に 'L' がある組を任意に選ぶとしても、最も右のものを選ぶ方法を並列処理しているだけ。
同時に交換可能な複数の組は要素を共有しないため、交換の順番を入れ替えても、特に影響はない。
したがって、好きな順で入れ替えを行ってよい。

これで複数の deque などでそろったデータを中抜きしつつシミュレーションすることが可能になった。
しかし、計算量が $O(N^2)$ になるため、残念ながら TLE になる。

ここから、これを高速化する。
$1$ つずつの 'R' に順番に注目し、それの移動回数の合計を高速に求める。

移動を $2$ 種類に分けて集計する。
'R' が移動する前にいたマスが、別の 'L' の目的地だったか、別の 'R' の目的地だったかで分ける。

まず、移動前の位置が、ある 'L' の目的地だった場合を考える。
これは、交換によって 'L' が 'L' （自身を含む）の目的地に乗る合計回数である。
自身を含まない分は、各 'L' の （目的地、現在地）という開区間の交錯数で求まる。
すなわち、値 $P_i$ と $P_j$ が位置 $i$ と $j$ にいて、$P_i<P_j<i<j$ である組数を求める。
ここに、各 'L' の自身の目的地に乗る分を足せば、目的のものが求められる。

次に、移動前の位置が、ある 'R' の目的地だった場合を考える。
最初から乗っていた分を除いた回数は、各 'R' の （現在地、目的地）という開区間の交錯数で求まる。
すなわち、値 $P_i$ と $P_j$ が位置 $i$ と $j$ にいて、$i<j<P_i<P_j$ である組数を求める。
ここに、各 'R' が最初から別の 'R' の目的地にいた数を足せば、目的のものが求められる。
（最後に足す分は、各 'R' ごと自分の目的地に 'R' がいる数としてカウントした方が扱いやすい）

交錯数については、開区間内に、他のものの現在地側だけ入っている個数を数えればよい。
これは、Fenwick木で現在地に $+1$、目的地に $-1$ しながら区間和を求めて処理していく。
'L' については左から、'R' については右から、これを行うことで合計交錯数が求まる。

Fenwick 木への加算と区間和の取得はそれぞれ $O(\log N)$ なので、全体の計算量は $O(N\log N)$ となる。

$\{3,5,4,1,2\}$ での動作

$N$ の値として $5$、順列 $P$ として $\{3,5,4,1,2\}$ を受け取った場合で例を示す。

まず、0-indexed にして、$\{2,4,3,0,1\}$ としておく。

前半として、Fenwick木 fl を用意して、左へ移動したいものを左から順に見ていく。

fl: {0,0,0,0,0} （実際にはFenwick木として対応する区間和を持っている、以下でも同様）

$i=0$ から $i=2$ は左へ移動したいものではないのでスキップ。

$i=3$ のとき、$0$ が位置 $3$ から位置 $0$ へ移動しようとしている。
区間の交錯数は fl の区間 $(0,3)$ の総和 $0$。
これと、自身の最後の移動分 $1$ を結果に加える。
区間 $(0,3)$ の情報を fl に乗せる。

result: 1
fl: {-1,0,0,1,0}

$i=4$ のとき、$1$ が位置 $4$ から位置 $1$ へ移動しようとしている。
区間の交錯数は fl の区間 $(1,4)$ の総和 $1$。
これは、先に見た $0$ が、$1$ の目的地である位置 $1$ を通る分である。
これと、自身の最後の移動分 $1$ を結果に加える。
区間 $(1,4)$ の情報を fl に乗せる。

result: 3
fl: {-1,-1,0,1,1}

後半として、Fenwick木 fr を用意して、右へ移動したいものを右から順に見ていく。

fr: {0,0,0,0,0}

$i=4$ と $i=3$ は右へ移動したいものではないのでスキップ。

$i=2$ のとき、$3$ が位置 $2$ から位置 $3$ へ移動しようとしている。
区間の交錯数は fr の区間 $(2,3)$ の総和 $0$。
目的地である位置 $3$ にある $0$ は L なので、最初から R が別の R の目的地に乗っている分は加えない。
区間 $(2,3)$ の情報を fr に乗せる。

result: 3
fr: {0,0,1,-1,0}

$i=1$ のとき、$4$ が位置 $1$ から位置 $4$ へ移動しようとしている。
区間の交錯数は fr の区間 $(1,4)$ の総和 $0$。
目的地である位置 $4$ にある $1$ は L なので、最初から R が別の R の目的地に乗っている分は加えない。
区間 $(1,4)$ の情報を fr に乗せる。

result: 3
fr: {0,1,1,-1,-1}

$i=0$ のとき、$2$ が位置 $0$ から位置 $2$ へ移動しようとしている。
区間の交錯数は fr の区間 $(0,2)$ の総和 $1$。
これは、$4$ が $2$ の目的地である位置 $2$ を通る分である。
また、目的地である位置 $2$ には、右へ移動しようとしている $3$ が最初から乗っている。
よって、さらに $1$ を結果に加える。
区間 $(0,2)$ の情報を fr に乗せる。

result: 5
fr: {1,1,0,-1,-1}

よって答えは $5$ となる。

注意点

答えは、int 型からはみ出る。
long long 型を用いること。

別解

公式解説にあるように、目的地までの距離合計から転倒数を引いても答えが出るらしい。
確認してみると正しいものの、一体どこからその計算の発想が……？