RMQ,ST表

快速查询区间的最大值
$O(nlogn)$ 预处理ST表， $O(1)$ 查询

来一发y总的代码，优雅！

#include <cstdio>
#include <cmath>

using namespace std;

const int N = 200010, M = 18; // log(200000) <= 18,f[]第二维空间

int n,m;
int w[N];
int f[N][M];

void init() // 初始化ST表，动态规划的思想
{
    for(int j = 0;j < M;j ++ ) // j 枚举区间长度
        for(int i = 1; i + (1 << j) - 1 <= n; i ++) // 下标从i开始，长度为2^j 的下标是 (i + 2^j) -1
            if(!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j-1], f[i + (1 << j -1)][j - 1]); // 区间对半分，取max, f[i + 2^{j-1}][j-1]
}

int query(int l,int r)
{
    int len=r-l+1;

    int k = log(len) / log(2); // 换底公式

    return max(f[l][k],f[r - (1 << k) + 1][k]); // 在[l,l+2^k] 和 [R - 2^k + 1,R] 取max
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    init();

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

    return 0;
}