CF2211C2 Equal Multisets (Hard Version) Solution

Ptll · 2026-03-30 15:15:56 · 题解

链接

题解

我们发现，对于 C1 只强调了是一个 1 到 n 的排列，所以这里是可以视作我要求弹出的 a_{i-k} 要和 b_{i-k} 相同，而 a_{i} 又必须和 b_i 相同。

对于这，实现是容易的，只需处理一下前 k 个点和后 k 个点的重合部分在处理一下其他地方即可。

思考完 C1 后，我们再来考虑 C2 的性质。

我们发现它要求变为 a_i \le n 我们又可以考虑对于 a，我新加入的数和原来的数是否相同。

• 相同

那这里只需要求 b_{i-k} = b_i 即可。

• 不同

那这里和 C1 的性质一样的，只需弹出和加入的数都得相同。

最后判断 b 中填入的数，是否和 a 中的数量相同即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template<typename T> void debug(T x) {
        cerr<<x<<'\n';
    }
    template<typename T> void debuglen(T x) {
        cerr<<x<<' ';
    }
    template<typename T,typename...Args> void debug(T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template<typename T> void debug(T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read() {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    void print(ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,k,a[N],b[N],cnt[N],pos[N];
inline void solve() {
    n=read(),k=read();
    for (ll i=1;i<=n;i++) {
        cnt[i]=pos[i]=0;
    }
    for (ll i=1;i<=n;i++) {
        a[i]=read();
    }
    for (ll i=1;i<=n;i++) {
        b[i]=read();
    }
    for (ll i=1;i<=k;i++) {
        ll pl=i,num=a[pl],sum=0;
        bool fl=1;
        while (pl<=n) {
            if (a[pl]!=num) {
                fl=0;
                break;
            }
            pl+=k;
        }
        if (!fl) {
            pl=i;
            while (pl<=n) {
                if (b[pl]!=-1&&b[pl]!=a[pl]) {
                    puts("NO");
                    return ;
                }
                pl+=k;
            }
            continue;
        }
        pl=i;
        sum=0;
        while (pl<=n) {
            if (b[pl]==-1) {
                pl+=k;
                continue;
            }
            if (!sum) {
                sum=b[pl];
            }
            else if (sum!=b[pl]) {
                puts("NO");
                return ;
            }
            pl+=k;
        }
        cnt[num]++;
        if (sum) {
            pos[sum]++;
        }
    }
    for (ll i=1;i<=n;i++) {
        if (pos[i]>cnt[i]) {
            puts("NO");
            return ;
        }
    }
    puts("YES");
}
int main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}