Mitsuami

2 secs 1024 MB

$Q \leq 100000$ より、 $1$ つのクエリ処理に $O(N)$ かけてはいけないと分かる。
それぞれにかかるスワップの最小回数から、自身がスワップされる回数も求めることができる。
$2$ つの紐を反転させるのに必要なスワップの回数は、 $1$ 回。
$3$ つの紐の時、題名通り三つ編みを実装しよう。
$\{1,2,3\}$ がある。これを $\{3,2,1\}$ にしたい時、

$1$ と $2$ をスワップ( $\{2,1,3\}$ になる)
$1$ と $3$ をスワップ( $\{2,3,1\}$ になる)
$2$ と $3$ をスワップ( $\{3,2,1\}$ になる)

これで、 $3$ 回の操作でできることがわかる。これが最短だということの証明は、転倒数を用いて行うことができる。

転倒数：
転倒(数学) - wikipedia
転倒数の概要とバブルソート・BITによる解法 | アウトプット雑記
 BITで転倒数を求める - Qiita
などを参考にしてください。

この「三つ編み方式」では $M$ 本の紐がある時全ての紐について $M-1$ 回スワップを行うことで高速に反転を行っている。
この問題の条件下で、最短の操作回数で操作を行うことと、すべての数に対してそれぞれ $($ 紐の数 $-1)$ 回スワップを行うことが同値だということは証明できる。
writerによる証明：数学的帰納法を用いた証明

証明

$N$ 個の数を題意における最小のスワップ回数反転させるときのそれぞれの数が移動する回数

$K=N$ と置く

$N=2$ の時、例えば $\{1,2\}$ を反転させるのには $1$ と $2$ を $1$ 回スワップさせれば良い

この時に $1,2$ はそれぞれ $1$ 回ずつスワップされているので成り立つ

$K=N$ のとき、これを証明した

$K=N+1$ の時、先に $N$ 個の数を反転させてから、最後に $N+1$ 個目の数を反対側の端に持っていくことを考える

先に行う操作で、 $N$ 個の数は $N-1$ 回スワップされている。

最後の操作で、端にある数 $N+1$ は、反対側まで移動するのに $N$ 回スワップを行わなければいけない。またこのとき、他の数は $1$ 回ずつスワップされている。

(これが最短なのは上に書いてあるはずの転倒数を用いると証明できる)

よって $K=N+1$ の時、全ての数は $N$ 回スワップされている。

証明終わり

よって、反転時にかかるコストは $L_i～R_i$ のそれぞれの数 $×(M -1)$ となる。
この区間和は、累積和を用いることで $O(1)$ で求めることができる。
計算量は $O(N+Q)$ です。

実装例(c++):こちら

Mitsuami

解説

証明