P2880 [USACO07JAN]平衡的阵容Balanced Lineup

yy2111 · 2020-02-26 18:52:11 · 个人记录

这个题就是来坑人的，，，， 明显的st表一个存最大值，一个存最小值 题面上给的数据范围是50000，我交上去后4个re， 然后我改成50w，就全AC，，，， 只能说坑人。。

#include<bits/stdc++.h>
using namespace std;
#define N 500005
int n,m,f1[N][30],f2[N][30];
int log1[N];
int main(){
    log1[0]=-1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        f1[i][0]=x;
        f2[i][0]=x;
        log1[i]=log1[i>>1]+1;
    }
    int M=log1[m];
    for(int j=1;j<=30;j++)
    for(int i=1;i+(1<<j)-1<=n;i++){
        f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
        f2[i][j]=min(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
    }
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int s=log1[y-x+1];
        int a=max(f1[x][s],f1[y-(1<<s)+1][s]);
        int b=min(f2[x][s],f2[y-(1<<s)+1][s]);
        printf("%d\n",a-b);
    }
    return 0;
}