雾粉与最小值(简单版)
链接: 牛客
思路
题意是 给定我们数组a让我们完成{x,l,r}询问,判断是否在a中存在子数组满足长度在l,r之间且子数组最小值大于等于x,输出yes 或者 no
一个数组,长度越长,其最小值越小,所以询问只有最小长度是有用的,我们只需要判断是否存在子数组满足最小值大于等于x且长度大于询问的最小长度即可,所以我们的工作就是算出满足大于等于x的子数组的最大长度,显然暴力n^2的时间复杂度铁超时,这时候我们回想算一个子数组的最大长度,不就是找它左边第一个大于他的右边第一个大于他的数的区间嘛,单调队列,两趟O(n)拿下,然后我们获得了每个a[i]的扩展长度,也就是子数组的最小是a[i]的最大长度,这时候我们就像二分大于x的值判断长度是否大于询问的最小值了,可是这时候二分出来的第一个大于x的长度是满足大于等于x的最大长度吗?比如询问的x是5,我们二分出来的是7,7的长度是4,但是后面还有8的长度是9,是不是就错误了,所以我们要把8的长度9加到7的长度上,所以我们还需要给a[i]和他的扩展长度按照a[i]递减排序,然后累计最长长度加到每个a[i]身上,这样我们就确保了二分出来的就是最大长度,这里我们为了方便可以使用map进行二分操作。
代码
#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 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;
}
文章评论