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; } }