【题解】Luogu P3865 【【模板】ST表】

终于过了ST的板,发现自己原来的板好像有问题,但是又找不出来,,,

于是就有了新的板:

#include<cstdio>
#include<cmath>

const int MAXN = 100000 + 6;
int f[MAXN][66],A[MAXN],n,m;

inline int max(int a,int b){
    return a > b ? a : b;
}

void STPrework(){
    for(int i = 1;i <= n;i++){
        f[i][0] = A[i];
    }
    for(int j = 1;(1 << j) <= n;j++){
        for(int i = 1;i + (1 << j) - 1 <= n;i++){
            f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
        }
    }
}
 
int STQuery(int l,int r){
    int k = 0;
    
    while((1 << k + 1) < r - l + 1){
        k++;
    }
    
    return max(f[l][k],f[r - (1 << k) + 1][k]);
}

int main(){
    scanf("%d %d",&n,&m);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&A[i]);
    }
    
    STPrework();
    
    for(int i = 0;i < m;i++){
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",STQuery(l,r));
    }
    
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

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