CFR 279 C. Ladder ( DP )

Problem - 279C - Codeforces
題意：
給一個序列 b 和若干筆詢問，對於每筆詢問 [ l, r ]，判斷是否存在一個 x，滿足 l ≤ x ≤ r 且 b1≤b[l+1]≤ b[l+2] ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ br。
解法：
對每個點預處理向右非遞減和非遞增各自能最多有多長。判斷的即是 l 向右非遞減延伸最長後，再由該處向右非遞增延伸最長，是否大於等於 r 。

int N, M;
vi A;

void init(){
    cin >> N >> M;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi dpu;
vi dpd;

void preprocess(){
    dpu = dpd = vi( N );
    for( int i = N - 1; i >= 1; --i ){
        if( A[ i - 1 ] <= A[ i ] )
            upmax( dpu[ i - 1 ], dpu[ i ] + 1 );
        if( A[ i - 1 ] >= A[ i ] )
            upmax( dpd[ i - 1 ], dpd[ i ] + 1 );
    }
}

void solve(){
    for( int i = 0; i < M; ++i ){
        int ql, qr; cin >> ql >> qr; --ql, --qr;
        const static string show[] = { "No", "Yes" };
        cout << show[ ql + dpu[ ql ] + dpd[ ql + dpu[ ql ] ] >= qr ] << endl;
    }
}