Với một phần tử có giá trị ~x~, nó chỉ có thể được hoán đổi trực tiếp với một phần tử có giá trị ~k - x~. Vì vậy, ta gom hai giá trị ~x~ và ~k - x~ vào cùng một ~\textbf{nhóm}~:

$$g(x) = \{\min(x, k - x), \max(x, k - x)\}$$

Nói cách khác, hai phần tử kề nhau chỉ có thể được hoán đổi nếu chúng thuộc cùng một nhóm.

Trước tiên, xét từng vị trí ~i~. Nếu ~a_i~ và ~b_i~ không thuộc cùng một nhóm, đáp án chắc chắn là ~\texttt{NO}~, vì các phần tử không thể di chuyển qua ranh giới giữa hai nhóm khác nhau.

Sau đó, ta chia mảng ~a~ thành các đoạn liên tiếp dài nhất sao cho mọi phần tử trong cùng một đoạn đều thuộc cùng một nhóm. Với mỗi đoạn như vậy, giả sử nhóm đang xét là ~\{x, k - x\}~, trong đó

$$x = \min(y, k - y)$$

với ~y~ là một giá trị bất kỳ trong đoạn.

Bên trong một đoạn, mọi phần tử đều chỉ là một trong hai giá trị ~x~ hoặc ~k - x~. Các phép hoán đổi hợp lệ cho phép ta đổi chỗ hai giá trị khác nhau đứng cạnh nhau, nên trong đoạn này, thứ tự cụ thể không quan trọng. Điều cần giữ lại chỉ là số lượng phần tử bằng ~x~.

Vì vậy, với mỗi đoạn ~[l, r)~, ta đếm số lần xuất hiện của ~x~ trong hai đoạn tương ứng:

$$\#x \text{ trong } a[l \dots r - 1] \quad \text{và} \quad \#x \text{ trong } b[l \dots r - 1]$$

Nếu hai số lượng này khác nhau ở bất kỳ đoạn nào, đáp án là ~\texttt{NO}~. Ngược lại, nếu mọi đoạn đều khớp, ta có thể biến đổi ~a~ thành ~b~.

Vì thuật toán chỉ duyệt qua mảng một số lần nhất định (hằng số), độ phức tạp là

$$O(n)$$

cho mỗi test.

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

using ll = long long;

pair<ll, ll> groupOf(ll x, ll k) {
    return {min(x, k - x), max(x, k - x)};
}

void solve() {
    int n;
    ll k;
    cin >> n >> k;

    vector<ll> A(n), B(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];

    for (int i = 0; i < n; i++) {
        if (groupOf(A[i], k) != groupOf(B[i], k)) {
            cout << "NO\n";
            return;
        }
    }

    int l = 0;
    while (l < n) {
        int r = l;
        auto g = groupOf(A[l], k);

        while (r < n && groupOf(A[r], k) == g) {
            r++;
        }

        ll x = g.first;

        int cntA = 0, cntB = 0;
        for (int i = l; i < r; i++) {
            if (A[i] == x) cntA++;
            if (B[i] == x) cntB++;
        }

        if (cntA != cntB) {
            cout << "NO\n";
            return;
        }

        l = r;
    }

    cout << "YES\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

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

}