Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-C2. Equal Multisets (Hard Version)(注意对子串变化的注意,虽然这个还是很容易注意到的) · znzryb
## 题目大意
**题目描述**
给定一个长度为 $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`。
## 思路讲解

```cpp
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代码
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)