【洛谷】P3865 【模板】ST 表

【洛谷】P3865 【模板】ST 表 题目地址：

https://www.luogu.com.cn/problem/P3865

题目描述：
给定一个长度为 N N N的数列，和 M M M次询问，求出每一次询问的区间内数字的最大值。

输入格式：
第一行包含两个整数 N , M N,M N,M，分别表示数列的长度和询问的个数。
第二行包含 N N N个整数（记为 a i a_i ai​），依次表示数列的第 i i i项。接下来 M M M行，每行包含两个整数 l i , r i l_i,r_i li​,ri​，表示查询的区间为 [ l i , r i ] [l_i,r_i] [li​,ri​]。

输出格式：
输出包含 M M M行，每行一个整数，依次表示每一次询问的结果。

数据范围：
对于 30 % 30% 30%的数据，满足 1 ≤ N , M ≤ 10 1le N,Mle 10 1≤N,M≤10。
对于 70 % 70% 70%的数据，满足 1 ≤ N , M ≤ 10 5 1le N,Mle {10}^5 1≤N,M≤105。
对于 100 % 100% 100%的数据，满足 1 ≤ N ≤ 10 5 1le Nle {10}^5 1≤N≤105， 1 ≤ M ≤ 2 × 10 6 1le Mle 2times{10}^6 1≤M≤2×106， a i ∈ [ 0 , 10 9 ] a_iin[0,{10}^9] ai​∈[0,109]， 1 ≤ l i ≤ r i ≤ N 1le l_ile r_ile N 1≤li​≤ri​≤N。

设数组为 A A A，令 f [ i ] [ j ] = max ⁡ A [ i : i + 2 j − 1 ] f[i][j]=max A[i:i+2^j-1] f[i][j]=maxA[i:i+2j−1]，从而有 f [ i ] [ 0 ] = A [ i ] f[i][0]=A[i] f[i][0]=A[i]， f [ i ] [ j ] = max ⁡ { f [ i ] [ j − 1 ] , f [ i + 2 j − 1 ] [ j − 1 ] } f[i][j]=max {f[i][j-1],f[i+2^{j-1}][j-1]} f[i][j]=max{f[i][j−1],f[i+2j−1][j−1]}，可以按照 j j j的递增顺序递推。对于询问，设 k k k是满足 2 k ≤ r − l + 1 2^kle r-l+1 2k≤r−l+1的最大正整数，则有 max ⁡ A [ l : r ] = max ⁡ { f [ l ] [ k ] , f [ r − 2 k + 1 ] [ k ] } max A[l:r]=max{f[l][k],f[r-2^k+1][k]} maxA[l:r]=max{f[l][k],f[r−2k+1][k]}代码如下：

#include 
#include 
using namespace std;

const int N = 1e5 + 10;
int n, m;
int f[N][20];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &f[i][0]);
    int J = log2(n);
    for (int j = 1; j <= J; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

    int l, r;
    while (m--) {
        scanf("%d%d", &l, &r);
        int k = log2(r - l + 1);
        printf("%dn", max(f[l][k], f[r - (1 << k) + 1][k]));
    }

    return 0;
}

预处理时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)，每次询问时间 O ( 1 ) O(1) O(1)，空间 O ( n log ⁡ n ) O(nlog n) O(nlogn)。