C1. Equal Multisets (Easy Version)

时间限制：2 秒
内存限制：256 MB

问题描述

这是该问题的简单版本。两个版本的区别在于：在本版本中，数组 $a$ 保证是一个排列。只有解决了本题所有版本的选手才能进行 hack。

给定一个大小为 $n$ 的数组 $a$ 和一个参数 $k$，称数组 $b$ 是 cool 的，如果满足以下条件：

• 对于每个 $i$ 从 $k$ 到 $n$，区间 $[a_{i-k+1}, a_{i-k+2}, \dots, a_i]$ 是 $[b_{i-k+1}, b_{i-k+2}, \dots, b_i]$ 的一个重排列。

给你两个大小为 $n$ 的数组 $a$ 和 $b$，以及一个整数 $k$。数组 $a$ 保证是一个排列 $^*$。数组 $b$ 只包含 $1$ 到 $n$ 之间的整数以及 $-1$。

判断是否可以将 $b$ 中所有的 $-1$ 替换为 $1$ 到 $n$ 之间的某个整数，使得 $b$ 关于 $k$ 是 cool 的。

$^*$ 一个长度为 $n$ 的排列是由 $n$ 个从 $1$ 到 $n$ 的不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数 $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$）。在本版本中，保证 $1$ 到 $n$ 的每个数恰好出现一次。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$ 或 $b_i = -1$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果可能则输出 YES，否则输出 NO。每个字母可以大写或小写。

样例输入

4
5 5
1 2 3 4 5
3 1 5 2 4
5 4
4 1 2 5 3
2 -1 -1 -1 -1
6 4
1 2 4 3 5 6
-1 -1 3 -1 -1 -1
6 4
1 2 4 3 5 6
-1 -1 3 3 -1 -1

样例输出

YES
NO
YES
NO

样例说明

在第一个测试用例中，$k = 5$。唯一的大小为 $5$ 的子数组是 $[1,5]$。可以看到 $b$ 是 $a$ 的一个重排列，因此答案为 YES。

在第二个测试用例中，可以证明无法替换 $b$ 中所有的 $-1$ 使得每个大小为 $k = 4$ 的子数组互为重排列。

WA 2 代码

// Problem: CF 2211 C1
// Contest: Codeforces - Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2211/problem/C1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

void solve(){
    int n,k;
    cin>>n>>k;
    map<int,PII> mp;
    vector<int> a(n+3);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int l=max(1,i-k+1);
        int r=min(n,i+k-1);
        mp[a[i]]={l,r};
    }
    vector<int> b(n+3),st(n+3,0);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(b[i]==-1) continue;
        if(st[b[i]]){
            cout<<"NO"<<endl;
            return ;
        }
        st[b[i]]=1;
    }

    for(int i=1;i<=n;i++){
        if(a[i]==b[i]) continue;
        if(b[i]==-1) continue;
        int l=max(1,i-k+1);
        int r=min(n,i+k-1);
        if(l>mp[b[i]].first || r<mp[b[i]].second){
            cout<<"NO"<<endl;
            return ;
        } 
    }
    cout<<"YES"<<endl;
    return ;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

AC 代码

// Problem: CF 2211 C1
// Contest: Codeforces - Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2211/problem/C1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+3),st(n+3,0),b(n+3);
    int l=n-k+1,r=k;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
        if(i>=l&&i<=r) st[a[i]]=1;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];  
    }

    int flag=1;
    for(int i=1;i<=n;i++){
        if(b[i]==-1) continue;
        if(i>=l&&i<=r){
            if(!st[b[i]]) flag=0;  //------
            continue;
        }
        if(a[i]!=b[i]) flag=0;
    }

    set<int> s;
    for(int i=l;i<=r;i++){
        if(b[i]==-1) continue;
        if(s.count(b[i])) flag=0;
        s.insert(b[i]);
    }

    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return ;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

📝 【算法笔记】滑动窗口不变量与区间锁定 (Sliding Window Invariant)

🏷️ 标签： #构造 #滑动窗口 #差分思维 #数学结论

💡 核心思想： 遇到“所有滑动窗口满足某条件”且涉及“排列/元素唯一性”时，不要看窗口的整体，看窗口滑动的边缘（差分）。

1. 经典模型 (The Model)

• 题目特征：给定一个数组 $A$（通常是排列或元素唯一），要求构造或验证另一个数组 $B$，使得对于所有长度为 $K$ 的滑动窗口，$A$ 和 $B$ 在该窗口内的元素集合（Multiset）完全相同。

• 思维误区：试图用线段树、哈希表或复杂的双指针去动态维护每一个窗口的具体内容（复杂度极高且容易写错边界）。

• 破局视角：从窗口 $W_i$ 滑动到 $W_{i+1}$ 时，发生变化的只有“出去的那个元素”和“进来的那个元素”。因为元素具有唯一性，这迫使两个数组在绝大多数位置上必须完全一致。

2. 核心推论：区间切割定理 (Interval Slicing)

对于一个长度为 $N$、滑动窗口大小为 $K$ 的数组，它天然会被切割成两种性质完全不同的区域：

🔒 绝对锁定区 (Locked Zone)

• 位置：i < N - K + 1 或 i > K

• 性质：这些位置的元素，有的只在某些特定窗口出现，有的在特定时刻进入或退出窗口。它们具有全场唯一的“窗口覆盖生命周期”。

• 结论：为了保证 $A$ 和 $B$ 的窗口集合严格一致，这一区域完全没有自由度，必须严格满足 B[i] == A[i]。

🕊️ 自由重排区 (Free Zone)

• 位置：N - K + 1 <= i <= K

• 性质：这些位置的元素，被所有的滑动窗口共同包含（它们是所有窗口的交集）。不管它们在交集内部怎么互换位置，都不会改变任何一个窗口的整体元素构成。

• 结论：这一区域拥有极高的操作自由度。B 在该区间的元素，可以是 A 在该区间元素的任意重排列。

• (注：如果 N - K + 1 > K，说明交集为空，即不存在自由区，整个数组必须完全锁死 A == B)。

3. 代码范式 (Code Paradigm)

对于此类验证问题，只需 $O(N)$ 的时间复杂度即可完成判定，核心分为三步检查：

C++

// 1. 划定边界
int L = N - K + 1;
int R = K;

// 2. 预处理自由区的合法集合
vector<int> st(N + 1, 0);
for (int i = L; i <= R; i++) {
    st[a[i]] = 1; // 记录自由区允许出现哪些元素
}

// 3. 线性扫描验证
bool ok = true;
set<int> used; // 用于检查自由区是否有重复填入的元素

for (int i = 1; i <= N; i++) {
    if (b[i] == -1) continue; // 待填空位直接跳过

    if (i >= L && i <= R) {
        // 【情况 A】当前位置在自由区
        if (!st[b[i]]) ok = false;       // 填入的元素根本不属于自由区集合
        if (used.count(b[i])) ok = false;// 填入的元素虽然合法，但被重复使用了
        used.insert(b[i]);
    } else {
        // 【情况 B】当前位置在锁定区
        if (b[i] != a[i]) ok = false;    // 必须严丝合缝地相等
    }
}

4. 教练复盘点评

这类问题的本质是寻找不变量 (Invariants)。在算法竞赛中，当约束条件看似多到“爆炸”（例如要求 $N-K+1$ 个窗口全都相等）时，通常意味着解空间极度狭窄。不要去模拟约束，而去反推：在如此严苛的约束下，谁还拥有自由？ 找到那个唯一的“自由区”，题目就迎刃而解了。

---

下一步训练建议

这两道题（B题的前缀和单调性、C1的差分锁定区）都在考察你对连续变化结构（前缀和、滑动窗口）的敏锐度。 接下来的几场训练，你可以有意识地去刷一些带有标签 constructive algorithms 并且 Rating 在 1500-1700 区间的题目。做题时，强迫自己在写下第一行代码前，先在纸上证明出解的下界或自由度边界。

准备好迎接下一个挑战了吗？随时把下一道题抛过来！