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

首先理解题意对于每一个查询找一个最小值大于等于val的子数组并且子数组的长度在minlen和maxlen之间。 那么首先对于一个值作为最小值求一个连续子数组的长度，这个就是单调栈的模板题，那么我们可以求出来每一个元素作为最小值得连续子数组的最大长度，然后对于每一查询需要看最小值大于等于val的所有子数组的长度是否小于minlen,小于直接打印no，否则就一定有一个区间符合。那么我们如何快速的找出大于val的所有子数组的最大值呢，这可以用树状数组或线段树做，这里提供一个树状数组的做法，树状数组求最大值的话，只能求0到i的最大值，那么我们就需要把每一个元素的大小进行反向映射,然后处理每一个查询。

#include <vector>
#include <stack>
#include <iostream>
#include <map>

using namespace std;

int main()
{
    stack<int> stk;
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector<int> left(n, -1), right(n, n);
    for(int i = 0; i < n; i+=1)
    {
        while(stk.size() && a[stk.top()] > a[i])
        {
            right[stk.top()] = i;
            stk.pop();
        }
        if(stk.size()) left[i] = stk.top();
        stk.push(i);
    }
    map<int, int> h;
    for(int i = 0; i < n; i++) h[a[i]] = max(h[a[i]], right[i] - left[i] - 1);
    map<int, int> h_idx;
    int j = 0;
    for(auto it = h.rbegin(); it != h.rend(); it++)
    {
        h_idx[it->first] = j++;
    }
    vector<int> tr(j + 1);
    auto insert = [&](int x, int c)
    {
        for(; x < tr.size(); x += x & -x) 
            tr[x] = max(tr[x], c);
    };
    auto query = [&](int x)
    {
        int res = 0;
        for(; x; x -= x & -x)
            res = max(res, tr[x]);

        return res;
    };  
    for(auto e : h_idx)
    {
        insert(e.second + 1, h[e.first]);
    }

    int q;
    cin >> q;
    while(q --)
    {
        int x, l, r;
        cin >> x >> l >> r;
        auto it = h.lower_bound(x);
        if(it == h.end()) cout << "No" << endl;
        else
        {
            int idx = h_idx[it->first] + 1;
            int res = query(idx);
            
            if(res < l) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }

    return 0;
}