热门景点题解

思路分析

题目意思并不难，就是如果对于每个查询区间，如果只存在一个极大值点（即 a_{i-1}\le a_i> a_{i+1} ），则输出Y，否则输N。

当然我们也可以发现，不满足条件的区间都至少存在一个极小值点（即 a_{i-1}>a_i\le a_{i+1} ），所以我们便可以预处理出每个极小值点，再对其做前缀和，如果满足 sum_{r-1}-sum_{l}\ge1 则我们可以说这个区间至少存在一个极小值点。预处理 O(n) ，查询 O(1) 。

这题并不难，主要是读入优化，普通的快读满足不了需求，需使用超快读 。

代码实现

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7+7;
int n,q,a[N],lmin[N],smin[N];
inline char bit(){
static char buf[1005],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1005,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
#define getchar() bit()
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
int main(){
    n=read();q=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
    }
    for(int i=2;i<=n-1;++i){
        if(a[i-1]>a[i]&&a[i]<=a[i+1]) lmin[i]=1;
      smin[i]=smin[i-1]+lmin[i];
    }
    for(int i=1;i<=q;++i){
        int l,r;
        l=read();r=read();
        if(abs(l-r)<=1){
            putchar('Y');putchar('\n');
            continue;
        }
        if(smin[r-1]-smin[l]<1){
            putchar('Y');putchar('\n');
        }
        else{
            putchar('N');putchar('\n');
        }
    }
    return 0;
}