题意：
给你长度为 \(N\) 的整数序列 \(A,B\) 以及整数 \(K\) 。
你可以执行下列操作零次或多次。
- 选择整数 \(i\) 和 \(j\) ( \(1 \leq i,j \leq N\) )。这里， \(|i-j| \leq K\) 必须保持不变。然后，将 \(A_{i}\) 的值改为 \(A_{j}\) 。
判断是否有可能使 \(A\) 与 \(B\) 相同。
分析：
做法参考了官方题解。
首先特判 \(A=B\) 的情况。其次如果 \(B\) 中存在了在 \(A\) 中没有出现的数字，直接输出 "No"。
时光倒流，将操作改为选择相同的 \(B_{i},B_{j}(|i-j| \le K)\)。然后把 \(B_{i}\) 变成 \(*\)（\(*\) 代表万能数字）。
如果一次都操作不了，直接输出 "No"。否则任意操作一次，因此接下来默认 \(B\) 中至少存在一个 \(*\)。
可以发现，\(B\) 的两个相邻的位置可以互相交换。原因如下：
-
当 \(B\) 中存在 \(*x\) 的情况，把 \(*\) 变成 \(x\)，然后操作一次变成 \(x*\)。因此 \(*\) 可以任意移动。
-
当 \(B\) 中存在 \(xy\) 的情况，先调一个 \(*\) 过来，变成 \(*xy\)，然后 \(*xy(yxy) \to yx*\)。不过需要满足 \(k \ge 2\)，因此最后要特判 \(k=1\) 的情况。
接下来只需要把 \(B\) 中相同的元素放在一堆 \(xxx\)，操作成 \(x**\)。然后把 \(B\) 中非 \(*\) 的匹配到 \(A\)，剩下的 \(*\) 直接变。所以直接输出 "Yes"。
如果 \(k=1\)，分别把 \(A,B\) 相邻的相同的元素合并成一个，操作后称为 \(A{'},B^{'}\)。那么 \(A\) 能操作成 \(B\) 当且仅当 \(B^{'}\) 是 \(A^{'}\) 的子序列。原因是显然的。
时间复杂度 \(O(Tn)\)。
分析：
#include<bits/stdc++.h>
#define int long long
#define N 300005
using namespace std;
int T, n, k;
int a[N], b[N], A[N], B[N];
vector<int>p[N];
bool z[N];
void Sol() {
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
bool flag = 1;
for(int i = 1; i <= n; i++)
if(a[i] != b[i]) {
flag = 0;
break;
}
if(flag) {
cout << "Yes" << endl;
return;
}
if(k == 1) {
int cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= n; i++) {
if(a[i] != a[i - 1]) A[++cnt1] = a[i];
if(b[i] != b[i - 1]) B[++cnt2] = b[i];
}
int now = 0;
for(int i = 1; i <= cnt1; i++) {
if(A[i] == B[now + 1]) {
now++;
if(now == cnt2) break;
}
}
if(now == cnt2) cout << "Yes" << endl;
else cout << "No" << endl;
}
else {
for(int i = 1; i <= n; i++) p[i].clear(), z[i] = 0;
for(int i = 1; i <= n; i++) z[a[i]] = 1;
for(int i = 1; i <= n; i++) {
if(!z[b[i]]) {
cout << "No" << endl;
return;
}
p[b[i]].push_back(i);
}
for(int i = 1; i <= n; i++) {
int len = p[i].size();
for(int j = 0; j < len - 1; j++)
if(p[i][j + 1] - p[i][j] <= k) {
cout << "Yes" << endl;
return;
}
}
cout << "No" << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while(T--) Sol();
return 0;
}