1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int m, n, a[maxn], log_2[maxn], mi[maxn][17];
int query(int l, int r) {
int k = log_2[r - l + 1];
return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
int main() {
cin >> m >> n;
int l, r;
for (int i = 1; i <= m; ++i) cin >> a[i];
for (int i = 2; i <= m; ++i) log_2[i] = log_2[i >> 1] + 1;
for (int i = 1; i <= m; ++i) mi[i][0] = a[i];
for (int j = 1; (1 << j) <= m; ++j) {
for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
}
}
while (n--) {
cin >> l >> r;
cout << query(l, r) << " ";
}
return 0;
}
|