Overview

Given the current permutation \(p\), determine whether it is possible to make it match the target permutation \(q\) by reversing exactly one contiguous subarray.

Observations

A reversal operation does not change any elements outside the chosen subarray.

Therefore, if there are positions where \(p\) and \(q\) differ, those positions must be included in the reversed subarray.

We think about it as follows:

• Let \(L\) be the first position from the left where \(p_i \neq q_i\)
• Let \(R\) be the first position from the right where \(p_i \neq q_i\)

In this case, the subarray that should be reversed is essentially \([L, R]\).

For example, given

\(p = [1, 2, 3, 4, 5]\)

\(q = [1, 4, 3, 2, 5]\)

the positions that differ are from position \(2\) to \(4\).

Reversing the subarray \([2, 3, 4]\) of \(p\) gives \([4, 3, 2]\), which matches \(q\).

On the other hand, an approach that tries all possible \(L, R\) pairs has \(O(N^2)\) candidate subarrays.
Since \(N \leq 10^6\), this approach would not be fast enough.

The key insight is that since elements outside the reversed subarray do not change, it is sufficient to look only at the first and last positions of mismatch.

Also, if \(p = q\) from the beginning, we can reverse a subarray of length \(1\) (where \(L = R\)), which does not change the arrangement, so the answer is Yes.

Algorithm

We determine the answer with the following steps:

1. Scanning from the left, find the first position \(L\) where \(p_i \neq q_i\).
2. If no such position exists, then \(p = q\) already, so output Yes.
3. Scanning from the right, find the first position \(R\) where \(p_i \neq q_i\).
4. Check whether reversing the subarray \([L, R]\) makes it match \(q\).

After reversal, the original \(p_i\) moves to position \(L + R - i\).

Therefore, if for all \(i\)

\(p_i = q_{L+R-i}\)

holds, then reversing the subarray \([L, R]\) produces a match.

The code checks this condition:

for (int i = L; i <= R; i++) {
    if (p[i] != q[L + R - i]) {
        cout << "No\n";
        return 0;
    }
}

If everything matches, output Yes.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

Array indices are handled as \(0\)-indexed in the code.

Also, even when \(p\) and \(q\) are already identical from the start, the operation must be performed “exactly once,” but since we can choose a reversal with \(L = R\), the arrangement does not change, so the answer is Yes.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> p(N), q(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    for (int i = 0; i < N; i++) cin >> q[i];

    int L = 0;
    while (L < N && p[L] == q[L]) L++;

    if (L == N) {
        cout << "Yes\n";
        return 0;
    }

    int R = N - 1;
    while (R >= 0 && p[R] == q[R]) R--;

    for (int i = L; i <= R; i++) {
        if (p[i] != q[L + R - i]) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.