给出 个整数
,
个查询,对于一个查询
,对应于子段
,需要你判断这个子段是不是单峰的。
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;
} 
京公网安备 11010502036488号