天才的记忆

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

Sparse Table 区间最大

一本通
练习

正文

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

天才的记忆

正文

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