P2880 [USACO07JAN]平衡的阵容Balanced Lineup

2020-1-18 13:59

1,107

未分类

61 字

几秒读完

链接：Miku

RMQ典型题

这道题询问最大值和最小值之差，那么我们知道最大值，最小值不就行了？

一个可以用st表，两个？两个st表。

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int st[1000001][50];
int st2[1000001][50];
int x,y;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        scanf("%d",&st[i][0]);
        st2[i][0]=st[i][0];
    }
    for(int i=1;i<=22;++i){
        for(int j=1;j+(1<<i)-1<=n;++j)
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    }
    for(int i=1;i<=22;++i){
        for(int j=1;j+(1<<i)-1<=n;++j)
            st2[j][i]=min(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        int k=log2(y-x+1);
        printf("%dn",max(st[x][k],st[y-(1<<k)+1][k])-min(st2[x][k],st2[y-(1<<k)+1][k]));
        }
        return 0;
}