数列区间最大值

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

Sparse Table 区间最大

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1541
// 题意：N 个数、M 次询问；每次问区间[X,Y]最大值；输出 M 行各一个数。
// 思路：Sparse Table 预处理区间最大值，O(1) 回答每个询问。
// 复杂度：O(N log N + M) 时间 / O(N log N) 空间
// 易错点：下标 1-based；询问区间 [X,Y] 右端含 Y。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005, LOG=17;
int st[MAXN][LOG+1], lg[MAXN];
int main(){
    int N,M;
    if(!(cin>>N>>M))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>>st[i][0];
    for(int j=1;j<=LOG;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    while(M--){
        int X,Y;cin>>X>>Y;
        int k=lg[Y-X+1];
        cout<<max(st[X][k],st[Y-(1<<k)+1][k])<<"\n";
    }
    return 0;
}

数列区间最大值

正文

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