CF2211C2（1800）

原题网址

题意不再赘述

  我们思考区间滑动的性质： 假设区间为[l,l+k],滑动至[l+1,l+k+1],此时a数组中减少了a_l，增加了a_r+1，b数组对应也减少了b_l，增加了b_r+1,题目要求滑动之后的窗口仍然为重排，这就意味着{a_l,a_r+1}={b_l,b_r+1}，此时可能有俩种情况：

1. a_l=b_l,a_r+1=b_r+1
2. a_l=b_r+1,a_r+1=b_l

这时我们可以将整个a数组分为k组，每组相邻的俩个数下标相差k，即T_i={a_i,a_i+k,a_i+2k...}(i∈1,2,3...k)此时题目可以转化为对于每组来说，要使Tib为Tia的重排

这时我们再讨论：

1. Tia中每个数都一样，此时Tib只要保证每个数都一样即可
2. Tia存在不一样的数，此时Tib的每一位都要与Tia相同

2的证明如下：假设a₁,a_1+k,a_1+2k为{1,1,2} 如果让b_1+k=2,b_1+2k=1，此时就后面俩个数来说是满足之前的关系的，但是如果考虑前面俩个数就会发现

{a₁,a_1+k}≠{b₁,b_1+k}因此我们要保证Tia的每一位都与Tib相同

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=2e5+5;
int n,k;
void solve(){cin>>n>>k;vector<int> a(n),b(n);for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];vector<int> st(k);unordered_map<int,int> mp;for(int i=0;i<k;i++){st[i]=a[i];for(int j=i+k;j<n;j+=k){if(a[j]!=st[i])st[i]=-1;}if(st[i]!=-1)mp[st[i]]++;else{for(int j=i;j<n;j+=k){if(b[j]!=-1 && b[j]!=a[j]){cout<<"NO\n";return;}}}}int cnt1=0;for(int i=0;i<k;i++){if(st[i]!=-1){set<int> v;for(int j=i;j<n;j+=k)v.insert(b[j]);v.erase(-1);if(v.size()>=2){cout<<"NO\n";return;}else if(v.size()==1){int x=*v.begin();if(!mp.count(x)){cout<<"NO\n";return;}else{mp[x]--;if(mp[x]==0)mp.erase(x);}}else cnt1++;}}int sum=0;for(auto it=mp.begin();it!=mp.end();it++){sum+=it->second;}if(cnt1==sum)cout<<"YES\n";else cout<<"NO\n";}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--)solve();
}