题意:
给出一列数,满足b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk的子段为Ladder.
给出一系列询问, 判断该子段是否构成Ladder.
思路:
朴素地想:
对于一个询问, 向右扫描,
若一直不减, yes.
若遇到第一个减少项, 则记录其前驱, 看此后是否一直不增. 若是, yes. 否则,no.
这样的话, 最多是O(n*m)的...1e10的数量级, 超时...
注意到询问是动态的, 而数列是静态的. 可以预处理, 记录下数列的性质, 查询的时候直接调用即可. 这里就用到了dp记忆化搜索...
首先考虑需要记录的性质是什么.
判断是否是ladder需要知道的信息是什么?
该点之后不增的最远点和不减的最远点...
dp[i].u dp[i].d
...但是这样好像并没有什么递推式...
看题解→ →
http://blog.sina.com.cn/s/blog_6ffc3bde01017jqj.html
题意：给一个数列，查询区间[l,r]内是否存在b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk或是非递增、非递减序列。
经常可以遇到这类问题，一般解法是求每个元素的单边最值区间或双边最值区间，我最初的想法是记录从每个元素开始，
在哪里开始递增和在哪里开始递减的，然后进行一系列纠结的运算。然后我看了看大神们的想法，果然很犀利，
只需要记录每个元素左边的递减区间和右边的递增区间，然后判断R[l]和L[r]的大小就可以了。
判断有没有交叠就可以了。
嗯,确实是这样.如果按原先的想法, 总是走一步判一步, 缺乏全局性, 而这种预处理是可以获得全局性质的. 因此需要记录的是全局性质.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int L[MAXN],R[MAXN];
//left non-increasing segment
//right non-decreasing segment
int a[MAXN],n,m;
void solve()
{
L[0] = 0;
for(int i=1;i<n;i++)
if(a[i]<=a[i-1]) L[i] = L[i-1];
else L[i] = i;
R[n-1] = n-1;
for(int i=n-2;i>=0;i--)
if(a[i]<=a[i+1]) R[i] = R[i+1];
else R[i] = i;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",a+i);
}
solve();
for(int i=0;i<m;i++)
{
int l,r;
scanf("%d %d",&l,&r);
if(R[--l]>=L[--r]) printf("Yes\n");
else printf("No\n");
}
}