单调队列 加 二分

雾粉与最小值(简单版)

链接： 牛客

思路

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

代码

#include
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;
}