https://codeforces.com/contest/279/problem/C
题意:给一个数列,查询区间[l,r]内是否存在b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk或是非递增、非递减序列
思路:
按照波峰的状态,预处理出每个点能往右达到的最远点/长度,每个点能往左达到的最远点/长度。
然后判[l,r]的区间长度是否满足r[l]+l[r]
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL r[maxn],l[maxn],a[maxn];
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m;cin>>n>>m;
for(LL i=1;i<=n;i++) cin>>a[i];
r[n]=0;
for(LL i=n-1;i>=1;i--){///每个点能向右延伸的长度
if(a[i]<=a[i+1]) r[i]=r[i+1]+1;
else r[i]=0;
}
l[1]=0;
for(LL i=2;i<=n;i++){///每个点能向左延伸的长度
if(a[i-1]>=a[i]) l[i]=l[i-1]+1;
else l[i]=0;
}
while(m--){
LL p,q;cin>>p>>q;
if(r[p]+l[q]>=(q-p)){
cout<<"Yes"<<"\n";
}
else cout<<"No"<<"\n";
}
return 0;
}