给出 个整数 , 个查询,对于一个查询 ,对应于子段 ,需要你判断这个子段是不是单峰的。
b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk
此处的单峰,指的是,开始时是一段单调不减的,然后以一段单调不增结束;同时这两段的长度为零也是可以的。
L[i] 表示i位置向前能走多远
R[i] 表示i位置向后能走多远
如果 R[r] + L[l] >= r - l + 1 表示是单存在当峰
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int a[maxn], L[maxn], R[maxn]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = n; i >= 1; i--) { if (a[i] > a[i + 1]) { L[i] = 1; } else { L[i] = L[i + 1] + 1; } } for (int i = 1; i <= n; i++) { if (a[i] > a[i - 1]) { R[i] = 1; } else { R[i] = R[i - 1] + 1; } } int l, r; while (m--) { cin >> l >> r; if (R[r] + L[l] >= r - l + 1) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }