题解 | 而后单调

// 若存在，则在原数组与排好序的数组中必存在一段是相同的，段长>=m，
// 可以用map或者二分快速定位到排好序的数组中，与原数组起点相同的位置，然后走一下这一段相同的有多长。
// 注意判断是否存在相同的数（严格单调），注意递增、递减排序都要判断一遍，递减不要用lower_bound
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+6;
int T;
int num1[N],num2[N],num3[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        unordered_set<int> unst;
        bool sign=true;
        for(int i=0;i<n;i++){
            cin>>num1[i];
            num2[i]=num1[i];
            num3[i]=num1[i];
            if(unst.count(num1[i])) sign=false;
            unst.insert(num1[i]);
        }
        if(!sign){
            cout<<"NO"<<endl;
            continue;
        }
        sort(num2,num2+n);
        sign=false;
        for(int i=0;i<n;i++){
            int idx=lower_bound(num2,num2+n,num1[i])-num2;
            int j=i;
            while(j<n && idx<n && num1[j]==num2[idx]){
                j++;
                idx++;
            }
            // cout<<i<<" "<<j<<endl;
            if(j-i>=m){
                sign=true;
                break;
            }
            i=j-1;
        }
        reverse(num2,num2+n);
        sort(num3,num3+n);
        for(int i=0;i<n;i++){
            int idx=lower_bound(num3,num3+n,num1[i])-num3;
            int j=i;
            idx=n-idx-1;
            while(j<n && idx<n && num1[j]==num2[idx]){
                j++;
                idx++;
            }
            // cout<<i<<" "<<j<<endl;
            if(j-i>=m){
                sign=true;
                break;
            }
            i=j-1;
        }
        if(sign) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}