单调队列 加 二分

雾粉与最小值(简单版)

链接： 牛客

思路

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

代码

#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 2for(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 2for(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;
}