原题 链接

条件：

注意到：随着子数组长度的增加，s(min)即子数组最小值会不变或者减小。可以用反证法证明这一
点，此处略。这个性质意味着如果有长度为L1的子数组最小值大于val，那么我们一定可以找到任意
的长度为L （L <= L1）且最小值大于val的子数组。

思路：

我们不是直接求出对于任一长度为L的子数组的最大min(s),而是对于每一个nums[i]，以下标i开始往两边寻找，能维持最小值为nums[i]的最大子数组长度。这个可以通过单调栈来处理,寻找对于nums[i]左右两边第一个小于nums[i]的数记录其下标，然后求出对于每个i所能维持的最大长度存入rec[i]中。
在求出这一步之后，还要做一个简单处理，就是改变rec[i]的含义，我们用rec[i]表示所形成子数组大于等于nums[i]的最大长度。
之后考虑如何回答询问，对于val , mn, mx 这样一组问询，我们首先查找第一个大于val的nums[i]，如果没有比val大的数，回答否,如果有，根据rec[i]的含义，直接判断rec[i] 是否不小于mn,是则可以找到一个长度大于mn且min(s)大于val的子数组，我们预先将nums[i] 和下标i放进pair里，然后排序,所以回答的时候二分查找即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
using i64 = long long;
using pt = std::pair<int, int>;
constexpr int MAXN = 1e6 + 10;
int nums[MAXN], f1[MAXN], f2[MAXN], rec[MAXN];
pt arr[MAXN];

void solve() 
{   
    int n;
    std::cin >> n;
    for(int i = 1; i <= n; i++)
    {
        std::cin >> nums[i];
        arr[i].first = nums[i];
        arr[i].second = i;
        f1[i] = f2[i] = -1;
        rec[i] = 1;
    }
    std::sort(arr + 1, arr + n + 1);
    
    std::stack<int> st;
    //右边第一个比我小的下标
    for(int i = 1; i <= n; i++)
    {
        while(st.size() && nums[st.top()] > nums[i])
        {
            int id = st.top();
            f2[id] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size()) st.pop();
    //左边第一个比我小的下标
    for(int i = n; i >= 1; i--)
    {
        while(st.size() && nums[st.top()] > nums[i])
        {
            int id = st.top();
            f1[id] = i;
            st.pop();
        }
        st.push(i);
    }
    //对于下标i，rec[i]记录他可以形成的以nums[i]为最小值的最长子数组长度
    for(int i = 1; i <= n; i++)
    {
        int l = f1[i] == -1 ? (i - 1) : (i - f1[i] - 1);
        int r = f2[i] == -1 ? (n - i) : (f2[i] - i - 1);
        rec[i] = l + r + 1;
    }
    for(int i = n - 1; i >= 1; i--)
    {
        int id1 = arr[i].second, id2 = arr[i + 1].second;
        rec[id1] = std::max(rec[id1], rec[id2]);
    }
    int m, val, mx, mn;
    std::cin >> m;
    while(m--)
    {
        std::cin >> val >> mn >> mx;
        int l = 0, r = n + 1;
        while(l + 1 != r)
        {
            int mid = l + ((r - l) >> 1);
            if(arr[mid].first < val)
                l = mid;
            else
                r = mid;
        }
        
        if(r == n + 1 || rec[arr[r].second] < mn)
        {
            std::cout << "No\n";
        }
        else
        {
            std::cout << "Yes\n";
        }
    }
}

signed main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    //std::cin >> t;
    while (t--)
    {   
        solve();
        std::cout << '\n';
    }
    return 0;
}