Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-C2. Equal Multisets (Hard Version)（注意对子串变化的注意，虽然这个还是很容易注意到的）

题目大意

题目描述
给定一个长度为 $n$ 的数组 $a$ 和一个参数 $k$。如果一个数组 $b$ 满足以下条件，则称其为“很酷的”：
对于从 $k$ 到 $n$ 的每个下标 $i$，子数组 $[a_{i-k+1}, a_{i-k+2}, \dots, a_i]$ 都是子数组 $[b_{i-k+1}, b_{i-k+2}, \dots, b_i]$ 的重新排列（即两个长度为 $k$ 的滑动窗口构成的多重集相同）。

现在给定数组 $a$ 和数组 $b$。数组 $a$ 仅包含 $1$ 到 $n$ 之间的整数；数组 $b$ 包含 $1$ 到 $n$ 之间的整数以及 $-1$。
请判断是否可以通过将 $b$ 中所有的 $-1$ 替换为 $1$ 到 $n$ 之间的任意整数，使得最终的数组 $b$ 满足上述“很酷的”条件。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$ 或 $b_i = -1$）。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式
对于每个测试用例，如果可以构造出满足条件的数组 $b$，输出 YES，否则输出 NO。

样例

Input
5
5 5
1 2 3 4 5
3 1 5 2 4
5 2
1 2 1 2 1
2 -1 -1 -1 -1
6 1
5 6 2 2 4 3
5 -1 -1 2 -1 3
2 1
1 2
2 -1
6 4
1 2 3 4 1 2
2 -1 3 -1 4 -1

Output
YES
YES
YES
NO
NO

样例解释第一个测试用例：$k=5$。唯一的长度为 $5$ 的子数组是整个数组本身。给定的 $b$ 已经是 $a$ 的一个重新排列，且没有 $-1$，满足条件，答案为 YES。
第二个测试用例：$k=2$。我们可以将所有的 $-1$ 替换，使得 $b = [2, 1, 2, 1, 2]$。此时在 $a$ 和 $b$ 中，每一个长度为 $2$ 的窗口要么是 $[1, 2]$ 要么是 $[2, 1]$，它们互为重新排列，因此答案为 YES。
第四个测试用例：$k=1$。长度为 $1$ 的窗口意味着对应位置的元素必须完全相同。因为已知 $a_1 = 1$ 而 $b_1 = 2$，两者不相等，所以无法满足条件，答案为 NO。

思路讲解

void Solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];

    // target: 第一个窗口 a[1..K] 的多重集，b[1..K] 也必须是它的一个排列
    map<ll, ll> target;
    for (int i = 1; i <= K; ++i) target[A[i]]++;

    // free_count: 第一个窗口中，值完全自由（可任意选取）的位置数
    int free_count = 0;

    // 按模 K 将位置分成 K 条链：链 r 包含位置 r, r+K, r+2K, ...
    // 每条链恰好有一个位置落在第一个窗口（即位置 r 本身）
    //
    // 关键推导：窗口从 [i, i+K-1] 滑到 [i+1, i+K] 时，
    //   需要 -{b_i} + {b_{i+K}} = -{a_i} + {a_{i+K}}
    // 因此：
    //   - 若 a_i ≠ a_{i+K}：必须 b_i = a_i 且 b_{i+K} = a_{i+K}
    //   - 若 a_i = a_{i+K}：只需 b_i = b_{i+K}（不一定等于 a）
    //
    // 对一条链来说：
    //   - 若链中存在相邻位置 a 值不同（"固定链"），则整条链的 b 值全部被唯一确定为 a 值
    //   - 若链中所有 a 值全相同（"自由链"），则链上所有 b 值必须相等，但具体取什么值是灵活的

    for (int r = 1; r <= K; ++r) {
        // 检查链 r 是否所有 a 值都相同
        bool all_equal = true;
        for (int p = r; p + K <= N; p += K) {
            if (A[p] != A[p + K]) { all_equal = false; break; }
        }

        if (!all_equal) {
            // 固定链：链上每个位置 b[p] 必须等于 a[p]
            // 检查已给定的 b 值是否与 a 一致
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1 && B[p] != A[p]) {
                    cout << "NO\n"; return;
                }
            }
            // 位置 r（第一个窗口中的位置）的 b 值确定为 a[r]，从 target 中扣除
            target[A[r]]--;
        } else {
            // 自由链：链上所有 b 值必须相等
            // 检查所有已给定的 b 值是否互相一致
            ll forced = -1;
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1) {
                    if (forced == -1) forced = B[p];       // 第一个给定值，记录
                    else if (forced != B[p]) {              // 与之前的给定值矛盾
                        cout << "NO\n"; return;
                    }
                }
            }
            if (forced != -1) target[forced]--;  // 链的值已确定，从 target 扣除
            else free_count++;                    // 链的值完全自由，待分配
        }
    }

    // 最终检查：target 中剩余的值（还没被匹配的）必须恰好分配给 free_count 个自由位置
    // 且不能有任何值被"过度消耗"（计数变负）
    ll remaining = 0;
    for (auto& [v, cnt] : target) {
        if (cnt < 0) { cout << "NO\n"; return; }
        remaining += cnt;
    }
    // 剩余的值刚好够填满所有自由位置 → YES，否则 → NO
    cout << (remaining == free_count ? "YES" : "NO") << "\n";
}

AC代码

源代码

心路历程（WA，TLE，MLE……）