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

PBP0001

ST算法模板

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;
}
点赞

发表评论

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