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)$ となる。

具体例での動作

次の場合を考える。

n: 5
p: {3, 5, 4, 1, 2}

0-indexed に直すと、次のようになる。

p: {2, 4, 3, 0, 1}

まず、左へ移動したい値を左から順に処理する。
Fenwick木では、処理済み区間の現在地に $+1$、目的地に $-1$ を加える。

$i=3$ では、値 $0$ が位置 $3$ から位置 $0$ へ移動したい。
開区間 $(0,3)$ の区間和は $0$ なので、交錯数は $0$ である。
自身が目的地へ移動する $1$ 回を加え、この値からの寄与は $1$ となる。

この区間の情報を加えた後の各位置への加算値は次のようになる。

{-1, 0, 0, 1, 0}

$i=4$ では、値 $1$ が位置 $4$ から位置 $1$ へ移動したい。
開区間 $(1,4)$ の区間和は $1$ なので、交錯数は $1$ である。
自身が目的地へ移動する $1$ 回も加え、この値からの寄与は $2$ となる。

この区間の情報を加えた後の各位置への加算値は次のようになる。

{-1, -1, 0, 1, 1}

ここまでの寄与は $1+2=3$ である。

次に、右へ移動したい値を右から順に処理する。
こちらも、処理済み区間の現在地に $+1$、目的地に $-1$ を加える。

$i=2$ では、値 $3$ が位置 $2$ から位置 $3$ へ移動したい。
開区間 $(2,3)$ の区間和は $0$ なので、交錯数は $0$ である。
目的地の位置 $3$ にある値 $0$ は左へ移動したいので、追加の寄与はない。

この区間の情報を加えた後の各位置への加算値は次のようになる。

{0, 0, 1, -1, 0}

$i=1$ では、値 $4$ が位置 $1$ から位置 $4$ へ移動したい。
開区間 $(1,4)$ の区間和は $0$ なので、交錯数は $0$ である。
目的地の位置 $4$ にある値 $1$ は左へ移動したいので、追加の寄与はない。

この区間の情報を加えた後の各位置への加算値は次のようになる。

{0, 1, 1, -1, -1}

$i=0$ では、値 $2$ が位置 $0$ から位置 $2$ へ移動したい。
開区間 $(0,2)$ の区間和は $1$ なので、交錯数は $1$ である。
さらに、目的地の位置 $2$ にある値 $3$ も右へ移動したいので、$1$ 回分を加える。
この値からの寄与は $2$ となる。

左向きの寄与 $3$ と右向きの寄与 $2$ を合わせると、答えは $5$ となる。

注意点

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

別解

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