Overview

Given two permutations \(p, q\), the problem asks whether we can transform \(p\) into \(q\) by reversing exactly one contiguous subarray.
We can solve this by finding the first and last positions where they differ, then checking whether that interval has a “reverse correspondence.”

Key Observations

The important observations are as follows:

• A single interval reversal only changes elements within some interval \([L, R]\)
• Therefore, the positions where \(p\) and \(q\) differ must form a single contiguous interval
• Specifically,
  • Let \(l\) be the first position from the left where they differ
  • Let \(r\) be the first position from the right where they differ
  • Then the candidate reversal interval is essentially determined as \([l, r]\)

The necessary conditions are: - Elements outside the interval already match (this is satisfied by the definition of \(l, r\)) - Elements inside the interval have reverse correspondence: \(p[l+i] = q[r-i]\) holds for all \(i\)

Simply checking this is sufficient.

Why a Naive Solution Doesn’t Work

Trying all \((L, R)\) pairs gives \(O(N^2)\) possibilities, and comparing after reversal takes \(O(N)\) each time, resulting in worst-case \(O(N^3)\), which is far too slow (\(N \le 10^6\)).
The key to this problem is using the property that “the mismatch interval is uniquely determined” to solve it in a single scan.

Algorithm

1. Scan from the left to find the first position \(l\) where \(p[l] \ne q[l]\).
2. If no such position is found (all elements match), we can satisfy “exactly one operation” by choosing \(L=R\), so output Yes.
3. Scan from the right to find the first position \(r\) where \(p[r] \ne q[r]\).
4. For the interval \([l, r]\), set pointers \(i=l, j=r\) and:
   • Check that \(p[i] == q[j]\) at every position while incrementing \(i\) and decrementing \(j\).
   • If any mismatch is found, output No.
5. If all checks pass, output Yes.

Example

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

• First mismatch: \(l=2\) (0-indexed)
• Last mismatch: \(r=4\)
• Comparisons:
  • \(p[2]=5\) and \(q[4]=5\)
  • \(p[3]=4\) and \(q[3]=4\)
  • \(p[4]=3\) and \(q[2]=3\)
• All match → Yes

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the input arrays)

Implementation Notes

• Don’t forget to return Yes when all elements already match (we can consider it as performing one operation with \(L=R\)).

• The reverse correspondence check is done by comparing p[i] with q[j] (there is no need to actually create a reversed array).

• Since the arrays are implemented with 0-indexing, pay attention to boundary conditions (such as i <= r).

  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;

    int i = l, j = r;
    while (i <= r) {
        if (p[i] != q[j]) {
            cout << "No\n";
            return 0;
        }
        ++i;
        --j;
    }

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

---

This editorial was generated by gpt-5.3-codex.