この問題は、全体で線形時間で解くこともできます。

長さ \(N\) の配列を持ち、それぞれの列に \(i\) が何回出現したかを管理することで、「それぞれの列に出現する値が多重集合として等しいか」や「同じ値が重複して出現するか」を \(\Theta(N)\) 時間で判定できます。

同じ値が重複しないとき、与えられた列は \(\{1,\ldots,N\}\) の置換です。 置換 \(i\mapsto P _ i\) が偶置換であるかは、\(P ^ {-1} _ {P _ i}=i\) なる逆置換 \(P ^ {-1}\) を持ちながらソートを行うことで \(\Theta(N)\) 時間で判定できます。 （置換を disjoint な巡回に分解することでも、線形時間で置換の偶奇を判定することができます。）

よって、この問題を \(\Theta(N)\) 時間で解くことができました。

実装例は以下のようになります。

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

int main() {
    using namespace std;

    unsigned N;
    cin >> N;
    vector<unsigned> A(N), B(N);
    for (auto &&a : A)
        cin >> a;
    for (auto &&b : B)
        cin >> b;

    // count_A[i] = (i が A に出現した回数)
    // count_B[i] = (i が B に出現した回数)
    vector<unsigned> count_A(N), count_B(N);
    for (auto &&a : A)
        ++count_A[--a];
    for (auto &&b : B)
        ++count_B[--b];

    // 多重集合として一致していないなら No
    if (count_A != count_B) {
        cout << "No" << endl;
        return 0;
    }
    // そうでなく、同じ要素が複数回出現していたら Yes
    if (*max_element(begin(count_A), end(count_A)) >= 2) {
        cout << "Yes" << endl;
        return 0;
    }

    // P[i] = B[A[i]] が偶置換 <=> A[i] と B[i] の置換の偶奇は等しい
    vector<unsigned> P(N), inv_P(N);
    transform(begin(A), end(A), begin(P), [&B](auto i) { return B[i]; });
    for (unsigned i{}; i < N; ++i)
        inv_P[P[i]] = i;

    bool ans{true};
    for (unsigned i{}; i < N; ++i)
        if (i != P[i]) {
            // P[i] と i を swap
            swap(inv_P[i], inv_P[P[i]]);
            swap(P[i], P[inv_P[P[i]]]);
            ans ^= true;
        }
    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}