【PB P0001】「一本通 4.2 例 1」数列区间最大值 ST算法

题目描述

输入一串数字,给你 $M$ 个询问,每次询问给你两个数字 $X, Y$,要求你说出 $X$ 到 $Y$ 这段区间内的最大数

输入格式

第一行两个整数 $N,M$ 表示数字的个数和要询问的次数,

接下来一行为 $N$ 个数,

接下来 $M$ 行,每行都有两个整数 $X, Y$。


ST算法模板

AC Code

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

int n, m;
int lg[MAXN], rmq[MAXN][21], a[MAXN];
void init() {
    lg[0] = -1;
    for(int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
            rmq[i][j] = max(rmq[i][j-1], rmq[i + (1 << j - 1)][j - 1]);
}

int getres(int l, int r) {
    int k = lg[r - l + 1];
    return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    init();
    for(int i = 1; i <= m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        printf("%d\n", getres(arg1, arg2));
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注