洛谷 P2880 [USACO07JAN]Balanced Lineup G (ST表模板)

题意:给你一组数,询问\(q\)次,问所给区间内的最大值和最小值的差.
题解:经典RMQ问题,用st表维护两个数组分别记录最大值和最小值然后直接查询输出就好了

代码:

int n,q;

int a[N];

int dp1[N][30],dp2[N][30];

int lg[N];

void lg_Init(){

    for(int i=1;i<=n;++i){

        int k=0;

        while(1<<(k+1)<=i) k++;

        lg[i]=k;

    }

}

void RMQ_Init1(){

    for(int i=1;i<=n;++i) dp1[i][0]=a[i];

    for(int j=1;(1<<j)<=n;++j){

        for(int i=1;i+(1<<j)-1<=n;++i){

            dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);

        }

    }

}

void RMQ_Init2(){

    me(dp2,INF,sizeof(dp2));

    for(int i=1;i<=n;++i) dp2[i][0]=a[i];

    for(int j=1;(1<<j)<=n;++j){

        for(int i=1;i+(1<<j)-1<=n;++i){

            dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);

        }

    }

}

int RMQ1(int l,int r){

    int k=lg[r-l+1];

    return max(dp1[l][k],dp1[r-(1<<k)+1][k]);

}

int RMQ2(int l,int r){

    int k=lg[r-l+1];

    return min(dp2[l][k],dp2[r-(1<<k)+1][k]);

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    n=read(),q=read();

    for(int i=1;i<=n;++i) a[i]=read();

    lg_Init();

    RMQ_Init1();

    RMQ_Init2();

    while(q--){

        int l,r;

        l=read(),r=read();

        printf("%d\n",RMQ1(l,r)-RMQ2(l,r));

    }

    return 0;

}

巴特西

洛谷 P2880 [USACO07JAN]Balanced Lineup G (ST表模板)

最新文章

热门文章