RMQ

动态规划 RMQ

RMQ-ST算法

const int maxn = 1000010;
int num[maxn];
int dp[maxn][30];
int n;
int main() {
    //input;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &num[i]);
        dp[i][0] = num[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 q, a, b;
    scanf("%d", &q);
    while (q --) {
        scanf("%d %d", &a, &b);
        int k = 0;
        while (a + (1 << k) - 1 <= b) k ++;
        k --;
        printf("%d\n", min(dp[a][k], dp[b-(1<<k)+1][k]));
    }
    return 0;
}