CodeForces 279C Ladder

比赛的时候又被数学题坑到了……

最后一场个人赛，并不知道是好是坏，但该来的还是要来……

题意：
给你一个序列，q个询问，每个询问为一个区间，问你这个区间的序列是否是Ladder序列。

所谓Ladder序列，就是A星序列，也可以说是峰型序列，包括非减和非增的断崖型。
比如说 1 2 2 1 或是 1 2 或是 2 1

思路：
我还在想到底得用什么数据结构……
实际上只要记录一下每个端点向左向右各能递减到的最大范围，再把端点值相加，看是否等于区间长度即可。

另一种想法是记录向左向右的峰，查询是检查两边中间的峰是否是同一个也可。

感觉第二个好理解一些。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int ldes[maxn];
int rdes[maxn];
int ary[maxn];

int main()
{
    int n, q, l, r;
    scanf("%d %d", &n, &q);
    each(i, n) scanf("%d", ary + i);
    each(i, n) if (ary[i - 1] >= ary[i]) ldes[i] = ldes[i - 1] + 1;
    else ldes[i] = 1;
    reach(i, n) if (ary[i] <= ary[i + 1]) rdes[i] = rdes[i + 1] + 1;
    else rdes[i] = 1;
    while (q--) {
        scanf("%d %d", &l, &r);
        if (ldes[r - 1] + rdes[l - 1] < r - l + 1)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}