2022/3/3 1638B.Reverse - プログラム色々

問題本文

長さnの順列 $p_{1},p_{2},...,p_{n-1},p_{n}$ が与えられます。 2つの整数 $l,r(1 \leq l \leq r \leq n)$ を選択し、順列の部分列 $[l,r$ ]を逆にする必要があります。

順列は、 $p_{1},p_{2},...,p_{l−1},p_{r},p_{r−1},...,p_{l},p_{r+1},p_{r+2},...,p_{n}$ になります。

最初の順列に対して正確に1つの逆演算を実行することによって取得できる、辞書式に最小の順列を見つけます。

同じ長さのaとbの2つの異なる順列の場合、最初の位置が異なる場合、aは辞書式順序でbよりも小さく、aの要素が小さいことに注意してください。

順列は、1からnまでの任意の順序のn個の異なる整数で構成される配列です。

たとえば、[2,3,1,5,4] は順列ですが、[1,2,2]は順列ではありません（2が配列に2回表示されます)。 [1,3,4] も順列ではありません（n = 3ですが、配列には4があります）。

入力各テストには、複数のテストケースが含まれています。

最初の行には、テストケースの数である単一の整数 $t(1\leq t\leq 500)$ が含まれています。

テストケースの説明は次のとおりです。

各テストケースの最初の行には、順列の長さである単一の整数 $n(1\leq n\leq 500)$ が含まれています。

各テストケースの2行目には、順列の要素であるn個の整数 $p_{1},p_{2},...p_{n} (1\leq pi \leq n)$ が含まれています。

出力テストケースごとに、取得できる辞書式順序で最小の順列を印刷します。

解答

$p_{i}$ を $p_{i}\neq i$ となる最初の要素とします。

要素のプレフィックス $p_{1} = 1,p_{2} = 2,...p_{i-1} = i-1$ の場合、すでに変更されているため、何も変更する必要はありません。

最小の辞書式順序ですが、その位置に $p_{i}ではなくi$ を使用したいと思います。

解決策は、セグメント $[i,j$ ] を逆にすることです。ここで、 $p_{j} = i$ です。

すべての $k \prec i$ に対して $p_{k} = k$ であるため、 $i \prec j$ であることに注意してください。

したがって、すべての $k \prec i$ に対して $p_{k} \prec p_{j} = i$ になります。

時間計算量：O(n)。