Overview

This is a problem where we need to determine whether the current student arrangement \(p\) can be made to match the target arrangement \(q\) by performing exactly one reversal operation on a contiguous interval.

Analysis

The key point in solving this problem is narrowing down the candidates for the interval to reverse.

1. Already matching case

If \(p\) and \(q\) are already completely identical from the start, according to the rule in the problem statement that “when \(L=R\), the arrangement does not change, but this is still considered as performing one operation,” we can achieve the goal by performing an operation with \(L=R\) at any position. Therefore, in this case the answer is always Yes.

2. Non-matching case

If \(p\) and \(q\) differ, there is at least one position where the elements are different. To make \(p\) match \(q\) through a reversal operation, we need to reverse “the entire range where \(p\) and \(q\) differ.”

Specifically, we can identify the candidate interval \([L, R]\) for reversal as follows: - Scanning from the left, let \(L\) be the first index where \(p_i \neq q_i\). - Scanning from the right, let \(R\) be the first index where \(p_i \neq q_i\).

If it is possible to make them match with a single reversal, the interval to reverse can only be this \([L, R]\). This is because: - If we include elements to the left of \(L\) or to the right of \(R\) in the reversal, elements that were originally matching would be moved to different positions. - Since \(p\) and \(q\) are permutations (each number from 1 to \(N\) appears exactly once), if we move an element from a position that already matches and bring a different element there, that position will necessarily become a mismatch.

Therefore, the problem can be solved by simply checking “whether the entire array matches \(q\) after reversing the identified interval \([L, R]\).”

Algorithm

1. Read arrays \(p\) and \(q\).
2. Compare from left to right and find the first index \(L\) where \(p[i] \neq q[i]\).
3. If all elements match, output Yes and terminate.
4. Compare from right to left and find the first index \(R\) where \(p[i] \neq q[i]\).
5. Reverse the elements of \(p\) from position \(L\) to position \(R\).
6. Check whether the reversed \(p\) completely matches \(q\). Output Yes if they match, No otherwise.

Complexity

Since \(N\) can be as large as \(10^6\), efficient processing is required. - Time complexity: \(O(N)\) - Array traversal (identifying \(L, R\)), reversal, and the final comparison can all be done in \(O(N)\). - Space complexity: \(O(N)\) - Required to store two arrays of length \(N\).

Implementation Notes

• Since \(N=10^6\), to prevent I/O from becoming a bottleneck, in C++ we use ios_base::sync_with_stdio(false); cin.tie(NULL); for speedup.

• Using std::reverse(p.begin() + L, p.begin() + R + 1); allows us to efficiently reverse the specified range.

• Comparing two vectors with p == q runs in \(O(N)\), making it convenient for checking after the reversal.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

/**
 * Problem: Determine if a permutation p can be transformed into permutation q
 * by reversing exactly one contiguous subarray [L, R].
 * 
 * Approach:
 * 1. If p and q are already identical, we can perform an operation where L = R.
 *    This satisfies the "exactly 1 operation" condition and leaves the array unchanged.
 *    Therefore, if p == q, the answer is "Yes".
 * 2. If p and q are different, let L_min be the first index where p[i] != q[i]
 *    and R_max be the last index where p[i] != q[i].
 * 3. Any single reversal that transforms p into q must cover at least the range [L_min, R_max].
 * 4. Since p and q are permutations (all elements are distinct), any reversal that 
 *    includes elements outside [L_min, R_max] would swap elements that already match, 
 *    making them no longer match (unless the segment is trivial, which brings us back to [L_min, R_max]).
 * 5. Thus, we only need to check if reversing the specific segment [L_min, R_max] in p results in q.
 * 
 * Complexity:
 * - Time: O(N), where N is the number of students (up to 10^6).
 * - Space: O(N) to store the permutations.
 */

using namespace std;

int main() {
    // Fast I/O is necessary for N = 10^6
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    // Read the current order p
    vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
    }

    // Read the target order q
    vector<int> q(N);
    for (int i = 0; i < N; ++i) {
        cin >> q[i];
    }

    // Find the first index L where p and q differ
    int L = -1;
    for (int i = 0; i < N; ++i) {
        if (p[i] != q[i]) {
            L = i;
            break;
        }
    }

    // If there are no differences, p == q.
    // An operation with L = R (e.g., L=1, R=1) is allowed and results in p == q.
    if (L == -1) {
        cout << "Yes" << endl;
        return 0;
    }

    // Find the last index R where p and q differ
    int R = -1;
    for (int i = N - 1; i >= 0; --i) {
        if (p[i] != q[i]) {
            R = i;
            break;
        }
    }

    // The only candidate operation that could potentially transform p into q
    // is reversing the segment from index L to R.
    reverse(p.begin() + L, p.begin() + R + 1);

    // After performing the reversal, check if the entire array p matches q.
    // In C++, comparing two vectors takes O(N) time.
    if (p == q) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.