概要

現在の順列 \(p\) の連続区間をちょうど \(1\) 回反転して、目標の順列 \(q\) にできるか判定します。
ポイントは、\(q\) の各要素が \(p\) のどの位置にあったかを見ることです。

考察

\(p\) の各値がどの位置にあるかを記録しておきます。
つまり、

\[ \mathrm{pos}[x] = p \text{ における } x \text{ の位置} \]

とします。

そして、\(q_i\) が \(p\) のどの位置にあったかを

\[ a_i = \mathrm{pos}[q_i] \]

とします。

例えば、

\[ p = [1, 2, 3, 4, 5, 6] \]

で、区間 \([2, 5]\) を反転すると、

\[ q = [1, 5, 4, 3, 2, 6] \]

になります。

このとき、\(q\) の各要素がもともと \(p\) の何番目にあったかを見ると、

\[ a = [1, 5, 4, 3, 2, 6] \]

です。

つまり、反転していない部分では \(a_i = i\) となり、反転した区間では位置が逆順になります。

区間 \([L, R]\) を反転した場合、次が成り立ちます。

• \(i < L\) または \(i > R\) の位置では変化しないので、\(a_i = i\)
• \(L \leq i \leq R\) の位置では反転するので、\(a_i = L + R - i\)

したがって、\(a_i\) は

そのまま / 連続した逆順区間 / そのまま

という形になっている必要があります。

素朴な方法が遅い理由

すべての区間 \([L, R]\) を試すと、区間の選び方は \(O(N^2)\) 通りあります。
さらに各区間について実際に反転後の配列を比較すると \(O(N)\) かかるため、全体で \(O(N^3)\) になってしまいます。

\(N \leq 10^6\) なので、この方法では間に合いません。

重要な気づき

最初に \(a_i \neq i\) となる位置を見つけたとします。
この位置は、反転区間の左端 \(L\) でなければなりません。

また、そのとき

\[ a_L = R \]

です。

なぜなら、反転後の位置 \(L\) には、もともと位置 \(R\) にいた要素が来るからです。

つまり、最初のズレを見つけた時点で、反転区間 \([L, R]\) は一意に決まります。
あとは、その区間内が正しく逆順になっているか、区間外がそのままかを確認すればよいです。

アルゴリズム

まず、\(p\) の各値の位置を記録します。

pos[p_i] = i

ただし、実装では \(0\) 始まりの添字を使っています。

次に、\(q\) を左から見ていきます。

各位置 \(i\) について、

a = pos[q_i]

を計算します。

まだ反転区間を見つけていない場合：

• \(a = i\) なら、その位置は一致しているのでそのまま進みます。
• \(a \neq i\) なら、ここが反転区間の左端 \(l\) です。
  • 右端は \(r = a\) と決まります。
  • このとき \(r \leq l\) なら不可能です。

反転区間を見つけた後：

• \(i \leq r\) の間は、反転区間の中です。
  • 正しく反転されているなら、

\[ a = l + r - i \]

でなければなりません。

• \(i > r\) なら、反転区間の外です。
  • そのため、

\[ a = i \]

でなければなりません。

最後まで条件を満たせば Yes、途中で条件を満たさなければ No です。

なお、最初から \(p = q\) の場合も Yes です。
問題では \(L = R\) の反転、つまり何も変化しない操作も許されているためです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

\(N\) が最大 \(10^6\) と大きいので、高速な入力処理を使っています。

また、\(q\) 全体を配列として保存する必要はありません。
\(q_i\) を読みながら、その場で pos[q_i] を確認して判定しています。

コード中では \(0\) 始まりの添字を使っているため、反転区間内の条件は

a == l + r - i

となります。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read() + b' '
    idx = 0

    def next_int():
        nonlocal idx
        while data[idx] <= 32:
            idx += 1
        x = 0
        while data[idx] > 32:
            x = x * 10 + data[idx] - 48
            idx += 1
        return x

    n = next_int()

    pos = [0] * (n + 1)
    for i in range(n):
        pos[next_int()] = i

    l = -1
    r = -1
    ok = True

    for i in range(n):
        a = pos[next_int()]

        if l == -1:
            if a != i:
                l = i
                r = a
                if r <= l:
                    ok = False
                    break
        elif i <= r:
            if a != l + r - i:
                ok = False
                break
        else:
            if a != i:
                ok = False
                break

    print("Yes" if ok else "No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。