Equal Multisets (Hard Version)

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7void solve() {
    8    int n, k; cin >> n >> k;
    9    vector<int> a(n), b(n);
    10    for (int i = 0; i < n; i++) cin >> a[i];
    11    for (int i = 0; i < n; i++) cin >> b[i];
    12    vector<int> tar(n + 1), used(n + 1);
    13    for (int i = 0; i < k; i++) { 
    14        tar[a[i]]++;
    15    }
    16    for (int i = 0; i < k; i++) {
    17        bool c = 1;
    18        int f = a[i];
    19        for (int j = i + k; j < n; j += k) {
    20            if (a[j] != f) {
    21                c = 0; 
    22                break;
    23            }
    24        }
    25        if (!c) {
    26            for (int j = i; j < n; j += k) {
    27                if (b[j] != -1 && b[j] != a[j]) {
    28                    cout << "NO" << '\n';
    29                    return;
    30                }
    31            }
    32            used[a[i]]++;
    33        } else {
    34            int val = -1;
    35            for (int j = i; j < n; j += k) {
    36                if (b[j] != -1) {
    37                    if (val == -1) {
    38                        val = b[j];
    39                    } else if (val != b[j]) {
    40                        cout << "NO" << '\n';
    41                        return;
    42                    }
    43                }
    44            }
    45            if (val != -1) {
    46                used[val]++;
    47            }
    48        }
    49    }
    50    for (int i = 1; i <= n; i++) {
    51        if (used[i] > tar[i]) {
    52            cout << "NO" << '\n';
    53            return;
    54        }
    55    }
    56    cout << "YES" << '\n';
    57}
    58int main() {
    59    ios::sync_with_stdio(0); cin.tie(0); 
    60    int t; cin >> t;
    61    while (t--) {
    62        solve();
    63    }
    64    return 0;
    65}