RMQ(区间最值问题)

通过ST表解决, 详见ST表吧, 给个模板

Code:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4;

int N;
int arr[maxn + 10];
int dp[maxn + 10][maxn + 10];

int RMQ(int l, int r) {
    int k = log2(r - l + 1);
    return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}

void RMQ_init() {
    for (int i = 1; i <= N; i++)
        dp[i][0] = arr[i];
    for (int j = 1; (1 << j) <= N; j++) {
        for (int i = 1; i + (1 << j) - 1 <= N; i++) {
            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
        }
    }
}

int T;

int main() {
    while (cin >> N) {
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
        }
        RMQ_init();
        int q;
        cin >> q;
        int a, b;
        for (int i = 1; i <= q; i++) {
            cin >> a >> b;
            cout << RMQ(a, b) << '\n';
        }
    }
    return 0;
}