かしのブログ

競技プログラミングとか

第三回アルゴリズム実技検定 N - 入れ替えと並び替え

AtCoder PAST 転倒数

問題

長さ $N$ の数列 $a = \{a_i | a_i = i\}$ に、以下の合計 $Q$ 個のクエリを実行した結果を求める。

$a_x$ と $a_{x+1}$ をスワップ
$a_x, a_{x+1}, \cdots, a_y$ を昇順に並び替える

考察

1つ目のクエリは $\mathcal{O}(1)$ で実行可能なので、2つ目のクエリを高速に行う方法を考える。

数列 $a$ の転倒数は、1つ目のクエリでは1増減し、2つ目のクエリでは発生するスワップの回数分だけ減少することがわかる。よって、全ての2つ目のクエリで発生するスワップの合計は高々 $Q$ 回であることがわかった。また、2つ目のクエリでは $a_i > a_{i+1}$ となる箇所でスワップされるので、このような $i$ の集合 $\mathcal{I}$ を知っておく必要がありそう。

1つ目のクエリで $a_x$ と $a_{x+1}$ をスワップすることを考える。 $a_i > a_{i+1}$ かどうかの関係が変わる可能性があるのは、 $(x-1, x), (x, x+1), (x+1, x+2)$ の3箇所なので、これらの関係が $a_i > a_{i+1}$ か判定し、 $\mathcal{I}$ を更新する。

2つ目のクエリで昇順にソートすることを考える。 $x \leq z \lt y \land z \in \mathcal{I}$ なる $z$ があるとき、 $a_z, a_{z+1}$ を更新し、 $(z-1, z), (z, z+1), (z+1, z+2)$ の関係を元に $\mathcal{I}$ を更新する。

setのデータ構造を用いると、上記の処理が $\mathcal{O}(Q \log Q)$ で十分高速に実行可能である。

実装