奶牛排队 Balanced Lineup

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 916 字

Sparse Table 区间极差

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1545
// 题意：N 头牛身高、Q 次询问；每次问区间[A,B]最高与最矮身高差；输出 Q 行。
// 思路：两个 Sparse Table 分别维护区间最大值与最小值，相减得极差。
// 复杂度：O(N log N + Q) 时间 / O(N log N) 空间
// 易错点：询问输出的是极差(最大值-最小值)；A,B 1-based 且 A<=B。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=50005, LOG=16;
int mx[MAXN][LOG+1], mn[MAXN][LOG+1], lg[MAXN];
int main(){
    int N,Q;
    if(!(cin>>N>>Q))return 0;
    lg[1]=0;
    for(int i=2;i<=N;i++)lg[i]=lg[i/2]+1;
    for(int i=1;i<=N;i++){cin>>mx[i][0];mn[i][0]=mx[i][0];}
    for(int j=1;j<=LOG;j++)
        for(int i=1;i+(1<<j)-1<=N;i++){
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    while(Q--){
        int A,B;cin>>A>>B;
        int k=lg[B-A+1];
        int hi=max(mx[A][k],mx[B-(1<<k)+1][k]);
        int lo=min(mn[A][k],mn[B-(1<<k)+1][k]);
        cout<<hi-lo<<"\n";
    }
    return 0;
}

奶牛排队 Balanced Lineup

正文

一本通·提高篇的其它内容