以下の2つの問題があります。それぞれどう解くでしょうか？
$N$を正の整数とする。$0,\ldots,N-1$を並び替えた順列を$a_0,\ldots,a_{N-1}$とする。
このとき、以下の操作を行うことができる
操作：$0\leq i\lt N-1$を一つ選んで、$a_i$と$a_{i+1}$をスワップする
$a_0,\ldots,a_{N-1}$をソートするために必要な操作回数の最小値を求めよ。
制約
$1\leq N\leq 2\times 10^5$
$(a_0,\ldots,a_{N-1})$は順列
$N$を正の整数とする。$0,\ldots,N-1$を並び替えた順列を$a_0,\ldots,a_{N-1}$とする。
このとき、以下の操作を行うことができる
操作：$0\leq i\lt j\leq N-1$を一つ選んで、$a_i$と$a_j$をスワップする
$a_0,\ldots,a_{N-1}$をソートするために必要な操作回数の最小値を求めよ。
制約
$1\leq N\leq 2\times 10^5$
$(a_0,\ldots,a_{N-1})$は順列
これら2つの問題の相違点は行える操作だけです。それ以外は全て同じ。
問題1の解答
これは競技プログラミングの典型で、バブルソートの交換回数と呼ばれるものです。単純に転倒数を求めればよいです。これはBITを使うことで計算ができます。
問題2の解答
これは、順列をサイクルに分解したときの$N-(サイクルの数)$で求めることができます。手法はいろいろありますが、UnionFindを使うと計算できます。
最後に
微妙に問題文を変えるだけで必要になってくるライブラリが全く別のになってしまうの、面白くないですか？
ちなみにライブラリの詳細→GitHub - shakayami/ACL-for-python
