雾粉与最小值(简单版)

点击获取更好的阅读体验

思路：

首先我们应该知道一个性质，在一个很长很长的数组里面，如果我们知道了所有长度为6的子数组的最小值的最大值是，那么长度小于6的所有子数组的最小值的最大值一定大于等于。 另外这道题给了minlen和maxlen，实际上我们能用到的只有minlen，和前面说的一样，长度小的子数组的最小值的最大值肯定大于等于长度大的子数组的最小值，实际上我们只需要看最小长度(minlen)的数组的最小值的最大值是否大于等于val即可。 于是我们可以预处理出来长度为p的数组最小值的最大值存在ans数组中即可。

具体实现：

通过拓展每个数的范围（左右拓展一个数组，这个数组满足最小值是当前这个数，并且这个数组是最长的），比如样例1 3 2，那最后一个数2可以是子数组3 2的最小值的最大值。

再显然一点9 8 7 6 5 6 7 8 9里面5可能作为ans[9]的答案，里面第一个6可能作为ans[4]答案，里面7可能是ans[3]的最大值，我们最后进行更新每个数，对每个p取最大值。

这个拓展的过程实际上就是找右边最后一个小于这个数的数的位置和左边第一个小于这个数的数的数的位置，这实际就是我们栈的应用的模板题，相信各位肯定能调的出来。

这样能保证更新到的ans[p]是最大值，但是有的p是不会被更新到的，比如1 1 1 1，只会更新ans[4]，但是ans[3]实际上也是1，所以需要倒着对ans[i]和ans[i+1]取max进行一波更新。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e9+7;
struct node
{
    int val,id;
};

void solve(){
    int n;cin>>n;
    int flag=1;
    vector<int> q(n+2,0);
    vector<int> ans(n+2,0),f(n+2,0),b(n+2,0);
    priority_queue<int,vector<int>,greater<int>> pq;
    map<int,int> mp;
    for(int i=1;i<=n;i++){
        cin>>q[i];
        pq.push(q[i]);
        mp[q[i]]++;
    }
    int cnt=1;
    stack<node> st;
    st.push({0,0});
    for(int i=1;i<=n;i++){
        int no=q[i];
        while(st.top().val>=no){
            st.pop();
        }
        f[i]=i-st.top().id-1;
        st.push({no,i});
    }
    while(st.size())st.pop();
    st.push({0,n+1});
    for(int i=n;i>0;i--){
        int no=q[i];
        while(st.top().val>=no){
            st.pop();
        }
        b[i]=st.top().id-i-1;
        st.push({no,i});
    }
    for(int i=1;i<=n;i++){
        int p=f[i]+b[i]+1;
        ans[p]=max(ans[p],q[i]);
    }
    for(int i=n;i>0;i--){
        ans[i]=max(ans[i],ans[i+1]);
    }
    int m;cin>>m;
    while(m--){
        int a,b,c;cin>>a>>b>>c;
        if(ans[b]>=a)cout<<"Yes\n";
        else cout<<"No\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    while(t--)solve();
}