题解：AT_arc183_b [ARC183B] Near Assignment

FS_NEO · 2025-11-26 17:34:58 · 题解

妙妙题。

先将 B 缩起来（颜色段缩成一个点），判掉颜色集不包含等显然的情况。

接下来处理 k=1。我们发现操作只能将颜色向两边推，不能改变顺序。则可行条件是 A 存在一个字串与缩小后 B 串相等。

如果 k\ge 2，考虑有连续的三个数 abc，可以通过操作产生 aab，baa。设 c 是无用的，则可以将与其相邻的两个数交换，也可以自己穿过两个数而不交换位置。

若缩小后 B 串长度小于 n，则答案一定可以。因为我们可以先构造出一个乱序的 B 串，然后用空着的位置排序。若等于 n，为了将 A 串排成 B 串的顺序，至少也得破坏一个点的数值。那个点需要在排序结束后用旁边相同颜色的点染回来。

/*

        2025.11.26

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=500005,inf=0x3f3f3f3f;
int n,a[MAXN],b[MAXN],tb[MAXN],tot,k;
map<int,int>vis,lst;
void solve(){
    vis.clear();lst.clear();
    cin>>n>>k;bool flag=1;tot=0;
    for(int i=1;i<=n;i++)cin>>a[i],vis[a[i]]=1,lst[a[i]]=-inf;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)if(a[i]!=b[i])flag=0;
    if(flag){cout<<"Yes\n";return ;}
    for(int i=1;i<=n;i++)if(b[i]!=b[i-1])tb[++tot]=b[i];
    for(int i=1;i<=n;i++)if(vis.find(b[i])==vis.end()){cout<<"No\n";return ;}
    if(k==1){
        int l=1;
        for(int i=1;i<=n;i++)if(l<=tot&&a[i]==tb[l])l++;
        if(l==tot+1)cout<<"Yes\n";
        else cout<<"No\n";
        return ;
    }
    if(tot==n){
        for(int i=1;i<=n;i++){
            if(i-lst[b[i]]<=k){cout<<"Yes\n";return ;}
            lst[b[i]]=i;
        }
        cout<<"No\n";
    }
    else cout<<"Yes\n";
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}