题解 | #E 而后单调#

E 而后单调

首先思考不可能的情况，分成两种：

• 存在重复元素，那么最后就不可能是严格单调增或者严格单调减的情况，因此
• 如果要满足题目要求，那么原数组必须要满足有至少长度为 的区间能和最后排好的某一段是能匹配的，如果不能就是

那么解法也很显然了，匹配的过程可以使用 或者二分查找+双指针优化。时间复杂度

写法一：二分+双指针

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int a[N], b[N];
int n, m;

int getPos(int x, int opt) {
    int l = 1, r = n;
    int pos = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (opt == 1) {
            // b递增
            if (b[mid] <= x) {
                l = mid + 1;
                pos = mid;
            } else r = mid - 1;
        } else {
            // b递减
            if (b[mid] >= x) {
                l = mid + 1;
                pos = mid;
            } else r = mid - 1;
        }
    }
    return pos;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i ++ ) {
        if (b[i] == b[i - 1]) {
            cout << "NO\n";
            return ;
        }
    }
    for (int i = 1; i + m - 1 <= n; i ++ ) {
        int j = i + 1;
        while (j <= n && getPos(a[j], 1) - 1 == getPos(a[j - 1], 1)) j ++;
        if (j - i >= m) {
            cout << "YES\n";
            return ;
        }
        i = j - 1;
    }
    reverse(b + 1, b + 1 + n);
    for (int i = 1; i + m - 1 <= n; i ++ ) {
        int j = i + 1;
        while (j <= n && getPos(a[j], 2) - 1 == getPos(a[j - 1], 2)) j ++;
        if (j - i >= m) {
            cout << "YES\n";
            return ;
        }
        i = j - 1;
    }
    cout << "NO\n";
}

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

写法二：map+双指针

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int a[N], b[N];
int n, m;
map<int, int> f;

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i ++ ) {
        if (b[i] == b[i - 1]) {
            cout << "NO\n";
            return ;
        }
    }
    for (int i = 1; i <= n; i ++ ) f[b[i]] = i;
    for (int i = 1; i + m - 1 <= n; i ++ ) {
        int j = i + 1;
        while (j <= n && f[a[j]] - 1 == f[a[j - 1]]) j ++;
        if (j - i >= m) {
            cout << "YES\n";
            return ;
        }
        i = j - 1;
    }
    reverse(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i ++ ) f[b[i]] = i;
    for (int i = 1; i + m - 1 <= n; i ++ ) {
        int j = i + 1;
        while (j <= n && f[a[j]] - 1 == f[a[j - 1]]) j ++;
        if (j - i >= m) {
            cout << "YES\n";
            return ;
        }
        i = j - 1;
    }
    cout << "NO\n";
}

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