题解 | 而后单调（平衡树）

#牛客春招刷题训练营# + 链接

想了半天最终决定还是暴力

题目没有保证输入不重复，先判重，重了肯定不能单调

然后遍历抽出哪一段，不在该段的全都插到平衡树里面，移动时只需要插一个数删一个数，单次复杂度O(logn)

每次遍历在平衡树中查询（最小数）和（最大数+1）的序号，如果相等则说明当前这段可以插入到排序后的数组里

另外，对于遍历的段，需要保证它本身是单调的，这个用简单计数器维护一下就可以了，具体可以看代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

int a[200010];
using namespace __gnu_pbds;
tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;

int main() {
    int T,n,m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) {
            scanf("%d", a+i);
        }
        std::unordered_set<int> st;
        bool bad=false;
        for (int i=1;i<=n;i++) {
            if (!st.insert(a[i]).second) {
                bad=true;
                break;
            }
        }
        if (bad) {
            puts("NO");
            continue;
        }        
        for (int i=n;i>m;i--) {
            tr.insert(a[i]);
        }
        // 单增=up, 单减=down
        int cntu = 0, cntd = 0;
        bool good = false;
        for (int i=2;i<m;i++) {
            if (a[i] <= a[i-1]) ++cntu;
            if (a[i] >= a[i-1]) ++cntd;
        }
        for (int i=m;i<=n;i++) {
            if (a[i] <= a[i-1]) ++cntu;
            if (a[i] >= a[i-1]) ++cntd;
            if (cntu==0) {
                // 验证单增
                if (tr.order_of_key(a[i-m+1]) == tr.order_of_key(a[i]+1)) {
                    good = true;
                    break;
                }
            }
            if (cntd==0) {
                // 验证单减
                if (tr.order_of_key(a[i]) == tr.order_of_key(a[i-m+1]+1)) {
                    good = true;
                    break;
                }
            }
            if (i<n) {
                if (a[i-m+2] <= a[i-m+1]) --cntu;
                if (a[i-m+2] >= a[i-m+1]) --cntd;
                tr.erase(a[i+1]);
                tr.insert(a[i-m+1]);
            }
        }
        if (good) puts("YES");
        else puts("NO");
        tr.clear();
    }
    return 0;
}