洛谷-P3865-ST表

问题

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

题目描述

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

输入格式

第一行包含两个整数 N, M ，分别表示数列的长度和询问的个数。

第二行包含 N 个整数（记为 $a_i$），依次表示数列的第 i 项。

接下来 M行，每行包含两个整数 $l_i,r_i$，表示查询的区间为$[l_i,r_i]$

输出格式

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

输入输出样例

输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出 #1

9
9
7
7
9
8
7
9

说明/提示

对于30%的数据，满足： $1 \leq N, M \leq 10$

对于70%的数据，满足： $1 \leq N, M \leq {10}^5$

对于100%的数据，满足：$1 \leq N \leq {10}^5, 1 \leq M \leq 2 \times {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N$

思路

一个序列的子区间个数显然有 $O(n^2)$ 个，根据倍增的思想，首先在这个规模为 $O(n^2)$ 的状态空间里选择一些 2 的整数次幂作为代表值。

设 $F[i, j]$ 表示数列 A 中下标在子区间 $[i, i+2^j-1]$ 里的数的最大值，也就是从 i 开始的 $2^j$ 个数的最大值。递推边界显然为 $F[i,0]=A[i]$，即数列 A 在子区间 $[i,i]$ 里的最大值。

在递推时，把子区间的长度成倍增长，有公式 $F[i, j] = max(F[i,j-1],F[i+2^{j-1},j-1])$，即长度为 $2^j$ 的子区间的最大值是两半长度为 $2^{j-1}$ 的子区间的最大值中的一个。

当查询任意区间 $[l,r]$ 的最大值时，先计算出一个 k ,满足 $2^k \le r-l+1 < 2^{k+1}$，也就是是 2 的 k 次幂小于区间长度的前提下最大的 k。那么“从 $l$ 开始的 $2^k$ 个数”和“以 $r$ 结尾的 $2^k$ 个数”这两段一定覆盖了整个区间 $[l,r]$，这来那个段的最大值分别为 $F[l,k]$ 和 $F[r-2^k+1,k]$，二者中较大的那个就是整个区间 $[l,r]$ 的最值。

题解

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
const int MAX = 1e5 + 5;
int a[MAX];
int n, m, l, r;
int f[MAX][17]; //f[i][j]表示 [i, i+2^j-1] 区间内的最大值

void ST_power() {
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j <= t; ++j)
        for (int i = 1; i <= n - (1 << j) + 1; ++i)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int ST_query(int l, int r) {
    int t = log(r - l + 1) / log(2);
    return max(f[l][t], f[r - (1 << t) + 1][t]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i + 1]);
    }
    ST_power();

    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", ST_query(l, r));
    }

    return 0;
}