题解 | 而后单调

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N], b[N];
int n, m;
map<int, int> posMap;

// 判断数组中是否存在重复元素
bool hasDuplicates() {
    sort(b + 1, b + n + 1);
    for (int i = 2; i <= n; i++) {
        if (b[i] == b[i - 1]) return true;
    }
    return false;
}

// 判断是否存在某个长度为 m 的连续子数组，原始顺序在排序后连续
bool checkValidSequence() {
    // 建立值到下标的映射（即 a[i] 在排序数组 b 中的下标）
    for (int i = 1; i <= n; i++) posMap[b[i]] = i;

    for (int i = 1; i + m - 1 <= n; i++) {
        int j = i + 1;
        // 如果当前元素在排序数组中是连续递增的
        while (j <= n && posMap[a[j]] - 1 == posMap[a[j - 1]]) j++;
        if (j - i >= m) return true;
        i = j - 1; // 跳过检查过的部分
    }
    return false;
}

// 单组测试数据处理函数
void solve() {
    cin >> n >> m;

    // 读入数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    // 如果有重复元素，不能构成严格单调序列
    if (hasDuplicates()) {
        cout << "NO\n";
        return;
    }

    // 升序检查
    if (checkValidSequence()) {
        cout << "YES\n";
        return;
    }

    // 降序检查
    reverse(b + 1, b + n + 1);
    if (checkValidSequence()) {
        cout << "YES\n";
        return;
    }

    cout << "NO\n";
}

// 主函数，处理多个测试用例
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        posMap.clear();  // 清空映射
        solve();
    }
    return 0;
}