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