luogu-HXOI U332989-身高

1
#include <iostream>
2
#include <cmath>
3

4
#define endl '\n'
5

6
using namespace std;
7

8
const int N = 1e6 + 5;
9
const int LN = log2(N) + 5;
10

11
int k, n, t;
12
int logx[N], f[N][LN];
13

14
inline void init() {
15
  logx[0] = -1;
16
  for (int i = 1; i <= n; ++i) {
17
    logx[i] = logx[i / 2] + 1;
18
  }
19

20
  for (int j = 1; j <= logx[n]; ++j) {
21
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
22
      f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
23
    }
24
  }
25
}
26

27
inline int query(const int &x, const int &y) {
28
  int j = logx[y - x + 1];
29
  return min(f[x][j], f[y - (1 << j) + 1][j]);
30
}
31

32
int main() {
33
  ios::sync_with_stdio(false);
34
  cin.tie(nullptr), cout.tie(nullptr);
35

36
  cin >> k >> n;
37
  for (int i = 1; i <= n; ++i) {
38
    cin >> f[i][0];
39
  }
40
  init();
41
  cin >> t;
42
  while (t--) {
43
    int l, r;
44
    cin >> l >> r;
45
    if (k >= query(l, r)) {
46
      cout << "Yes" << endl;
47
    } else {
48
      cout << "No" << endl;
49
    }
50
  }
51
}