题解 | 而后单调

#include <iostream>
#include <map>
#include <vector>
using namespace std;
/*
 最朴素的想法。如果而后单调，那么肯定满足一下条件：
 1. 不包含重复元素。
 2. 原始数组存在一个至少长度为m的严格递增或者递减序列。

 这里我们使用map记录元素值和元素原始序号，map会自动根据插入的key排序，所以最终的map为递增key，如果想要满足2条件，只需要验证存在至少长度为m的value的数值（即原始序号）为严格递减或者递增。
*/

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        map<int, int> mm;

        for (int i = 0; i < n; i++) {
            int t;
            cin >> t;
            mm.insert(make_pair(t, i));//记录元素数值和原始序号
        }
        if (n!=mm.size()) {
            //如果这里，说明存在重复元素，直接NO
            cout<<"NO"<<endl;
            continue;
        }
        if (m==1) {
            //如果m=1直接YES
            cout<<"YES"<<endl;
            continue;
        }
        int front = -1;//记录上一个元素数值
        int si_s = 1;//记录递增序列大小
        int si_j = 1;//记录递减序列大小
        bool f = false;//记录是否找到m个单调序列
        for (auto p : mm) {
            if (front == -1) {
                front = p.second;
                continue;
            }
            //判断是否严格递增
            if ((p.second - front) == 1) {
                si_s++;
                si_j = 1;
                if (si_s == m) {
                    cout << "YES" << endl;
                    f = true;
                    break;
                }
            } else {
                si_s = 1;
            }
            //判断是否严格递减
            if ((p.second - front) == -1) {
                si_j++;
                si_s = 1;
                if (si_j == m) {
                    f = true;
                    cout << "YES" << endl;
                    break;
                }
            } else {
                si_j = 1;
            }
            front = p.second;
        }
        if (!f) {
            cout << "NO" << endl;
        }

    }
}