题解 | #雾粉与最小值(简单版)#

C题 思路：二分+ST表

处理st表，接着二分每一个a[i]两边能扩展的最大长度，然后记录a[i]所能扩展的最大长度。排序，处理一个后缀最大数组，然后对于每一个询问，二分到第一个位置询问后缀最大值是否符合长度大于l。

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

template<class T>
struct ST {
    vector<vector<T>> st;
    ST(const vector<T> &s) {
        const int n = s.size() - 1;
        st.assign(n + 1, vector<T>(22, 0));
        for (int i = 1 ; i <= n ; ++i) {
            st[i][0] = s[i];
        }
        for (int j = 1 ; j <= __lg(n) ; j++) {
            for (int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
                st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    T query(int L, int R) {
        int k = __lg(R - L + 1);
        return min(st[L][k], st[R - (1 << k) + 1][k]);
    }
}; // SparseTable
signed main(){
    int n;cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    ST st(a);
    int m;cin >> m;
    map<int,int>mp;
    for(int i = 1; i <= n; i++){
        int mi = a[i];
        int l = 1, r = i;
        int len = 1;
        while(l < r){
            int mid = l + r >> 1;
            if(st.query(mid, i) >= mi){
                r = mid;
            }
            else l = mid + 1;
        }
        len += i - l;
        l = i, r = n;
        while(l < r){
            int mid = l + r + 1 >>1;
            if(st.query(i, mid) >= mi){
                l = mid;
            }
            else r = mid - 1;
        }
        len += l - i;
        mp[a[i]] = max(mp[a[i]], len);
    }
    sort(a.begin() + 1, a.end());
    vector<int>nm(n + 2);
    for(int i = n; i >= 1; i--){
        nm[i] = max(nm[i + 1], mp[a[i]]);
    }
    while(m--){
        int val, l, r;
        cin >> val >> l >> r;
        int x = lower_bound(a.begin() + 1, a.end(), val) - a.begin();
        if(nm[x] >= l){
            cout <<"Yes" <<endl;
        }
        else cout <<"No" << endl;
    }
    return 0;
}