AtcoderABC245场

**AtCoder ABC245**

### **E. Array Transformation**

#### **Problem Statement**

You are given an array $a$ of length $n$, and a sequence of operations that can be applied to it. In each operation, you choose a subarray $[l,r]$ (for $1leq lleq rleq n$) and replace it with the concatenation of two arrays: the first one is obtained by reversing the subarray $a[l+1..r]$, and the second one is the subarray $a[r+1..n]$.

For example, if we have an array $[1,2,3,4,5]$ and we apply the operation to the subarray $[2,5]$, then it will be transformed into $[1,5,4,3,2,5]$.

Your task is to determine whether it's possible to transform the given array $a$ into the target array $b$ using a sequence of operations. You can apply an operation any number of times (including zero), and you must apply all operations in order from left to right.

#### **Constraints**

* $1leq nleq2times10^5$
* $a_i,b_iin mathbb{Z}$#### **Input Format**

The first line contains a single integer $n$ ($1leq nleq2times10^5$).

The second line contains $n$ integers $a_1,a_2,ldots,a_n$, where each $a_i$ is an integer.

The third line contains $n$ integers $b_1,b_2,ldots,b_n$, where each $b_i$ is an integer.

#### **Output Format**

If it's possible to transform the array $a$ into the target array $b$, print "YES". Otherwise, print "NO".

### **Solution**

cpp#include <iostream>
#include <vector>

using namespace std;

const int N =2e5 +10;
int n, a[N], b[N];

bool check(int l, int r) {
 if (l == r)
 return true;
 int mid = (l + r) /2;
 bool flag = false;
 for (int i = l; i <= mid; ++i)
 if (a[i] != b[i])
 flag = true;
 for (int i = mid +1; i <= r; ++i)
 if (a[i] != b[i])
 flag = true;
 return check(l, mid) && check(mid +1, r) && !flag;
}

void solve() {
 cin >> n;
 for (int i =1; i <= n; ++i)
 cin >> a[i];
 for (int i =1; i <= n; ++i)
 cin >> b[i];

 if (check(1, n)) {
 cout << "YES" << endl;
 } else {
 cout << "NO" << endl;
 }
}

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

 int T =1;

 while (T--) {
 solve();
 }

 return0;
}

### **Explanation**

This solution uses a recursive approach to check if the array `a` can be transformed into the target array `b`. The function `check(l, r)` checks if the subarray from index `l` to `r` can be transformed. If `l == r`, it means there is only one element in the subarray, so we return true.

Otherwise, we find the middle index `mid` and check two parts: the left part from index `l` to `mid` and the right part from index `mid +1` to `r`. We also need to ensure that the elements in these two parts are not changed during the transformation. If both parts can be transformed, we return true.

In the main function, we first read the array `a` and the target array `b`. Then we call the function `check(1, n)` to check if the entire array `a` can be transformed into the target array `b`.

If it's possible to transform the array `a` into the target array `b`, we print "YES". Otherwise, we print "NO".

Note that this solution assumes that the input arrays are valid and do not contain any invalid or out-of-range values.