提出コード

2つの要素$a_l$と$a_r$をSwapしたとき、$a_r > a_l$であれば、 ある範囲ではPrefixSumが増加し、それ以外では変化しないということになる。 つまり、単純に固定されていない要素を降順に並べ替えればよい。

  • $0 \sim l-1$の範囲ではPrefixSumの変化なし
  • $l \sim r-1$の範囲ではPrefixSumが$+(a_r-a_l)$増加する
  • $r \sim n-1$の範囲ではPrefixSumの変化なし