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

C题。考虑从小到大插入每一个数，然后计算一下每个数之间的最大长度是多少，用set维护一下已经插入的位置，再用multiset维护一下所有区间的长度，最后询问的时候二分一下就行。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int MAXN=2e5+5;
void solve()
{
    int n;
    cin>>n;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i].first;
        a[i].second=i+1;
    }
    bool L=0,R=0;
    sort(a.begin(),a.end());
    vector<int> num(n);
    multiset<int> q;
    set<int> s;
    for(int i=0;i<n;i++)
    {
        if(i==0)
        {
            int x=a[i].second-1,y=n-a[i].second;
            q.insert(a[i].second-1);
            q.insert(n-a[i].second);
            s.insert(a[i].second);
            num[i]=*q.rbegin();
            continue;
        }
        auto l=prev(s.upper_bound(a[i].second));
        auto r=s.upper_bound(a[i].second);
        // if(i==2)
        // {
        //     cout<<*s.begin()<<endl;
        //     cout<<a[i].second<<endl;
        // }
        if(*s.begin()>a[i].second)
        {
            int len=*r-1,x=*r-a[i].second-1,y=a[i].second-1;
            if(q.find(len)!=q.end()) q.erase(q.find(len));
            q.insert(*r-a[i].second-1);
            q.insert(a[i].second-1);
            s.insert(a[i].second);
            num[i]=*q.rbegin();
            continue;
        }
        if(r==s.end())
        {
            int len=n-*l,x=n-a[i].second,y=a[i].second-*l-1;
            if(q.find(len)!=q.end()) q.erase(q.find(len));
            q.insert(n-a[i].second);
            q.insert(a[i].second-*l-1);
            s.insert(a[i].second);
            num[i]=*q.rbegin();
            continue;
        }
        int len=*r-*l-1,x=*r-a[i].second-1,y=a[i].second-*l-1;
        if(q.find(len)!=q.end()) q.erase(q.find(len));
        q.insert(*r-a[i].second-1);
        q.insert(a[i].second-*l-1);
        s.insert(a[i].second);
        num[i]=*q.rbegin();
    }
    vector<int>temp;

    for(int i=0;i<n;i++) temp.push_back(a[i].first);

    int m;
    cin>>m;
    while(m--)
    {
        int v,l,r;
        cin>>v>>l>>r;
        int pos=lower_bound(temp.begin(),temp.end(),v)-temp.begin();
        if(pos==n)
        {
            cout<<"No\n";
            continue;
        }
        int len;
        if(pos==0)
        {
            len=n;
        }
        else len=num[pos-1];
        if(len>=l)
        {
            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();
    return 0;
}