单调队列 加 二分

雾粉与最小值(简单版)

链接： 牛客

思路

题意是 给定我们数组a让我们完成{x,l,r}询问，判断是否在a中存在子数组满足长度在l,r之间且子数组最小值大于等于x，输出yes 或者 no
一个数组，长度越长，其最小值越小，所以询问只有最小长度是有用的，我们只需要判断是否存在子数组满足最小值大于等于ｘ且长度大于询问的最小长度即可，所以我们的工作就是算出满足大于等于ｘ的子数组的最大长度，显然暴力ｎ＾２的时间复杂度铁超时，这时候我们回想算一个子数组的最大长度，不就是找它左边第一个大于他的右边第一个大于他的数的区间嘛，单调队列，两趟Ｏ（ｎ）拿下，然后我们获得了每个ａ［ｉ］的扩展长度，也就是子数组的最小是ａ［ｉ］的最大长度，这时候我们就像二分大于ｘ的值判断长度是否大于询问的最小值了，可是这时候二分出来的第一个大于ｘ的长度是满足大于等于ｘ的最大长度吗？比如询问的ｘ是５，我们二分出来的是７，７的长度是４，但是后面还有８的长度是９，是不是就错误了，所以我们要把８的长度９加到７的长度上，所以我们还需要给ａ［ｉ］和他的扩展长度按照ａ［ｉ］递减排序，然后累计最长长度加到每个ａ［ｉ］身上，这样我们就确保了二分出来的就是最大长度，这里我们为了方便可以使用ｍａｐ进行二分操作。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;
struct node{
    int x, y;
    bool operator < (node & tem)
    {
        if(x != tem.x)
        return x > tem.x;
        return y > tem.y;
    }
};
// 单调栈
int l[N], r[N], len[N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    stack<int> st;// 找离a[i]最近的小于a[i]的最左位置
    //6 4 3 6维护一个单调减数列  1 3 2
    for(int i = 1; i <= n; i ++)
    {
        while(st.size() && a[st.top()] >= a[i])
        {
            st.pop();
        }
        if(st.size()) l[i] = st.top()+1;
        else l[i] = 1;
        st.push(i);
    }
   // 找a[i] 右边最右的大于a[i]的元素
  
    stack<int> s;//1 2 3 8 2
    for(int i = n; i >= 1; i --)
    {
        while(s.size() && a[s.top()] >= a[i])
        {
            s.pop();
        }
        if(s.size()) r[i] = s.top()-1;
        else r[i] = n;
        s.push(i);
    }
        vector<node> c;
    for(int i = 1; i <= n; i ++)
    {
       len[i] = r[i] - l[i] + 1;
        c.push_back({a[i], len[i]});
    }
    sort(c.begin(), c.end());
    int maxlen = 0;
    map<int, int> cnt;
    for(int i = 0; i < c.size(); i ++)
    {
        maxlen = max(maxlen, c[i].y);
        if(!cnt.count(c[i].x)) cnt[c[i].x] = maxlen;
    }
    cin >> m;
    for(int k = 1; k <= m; k ++)
    {
        int x, ll, rr; cin >> x >> ll >> rr;
        auto res = cnt.lower_bound(x);
        if(res == cnt.end() || (res->second) < ll) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}