RMQ模板-526互联

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int lg[N];
int f[N][M];
//查询区间最值
//预处理f数组
void init()
{
	lg[1]=0;
	for(int i=2;i<=N;i++)lg[i]=lg[i>>1]+1;//预处理对数数组
	//f数组的含义区间以i开头，长度为2的j次方的区间的最大值
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k =lg[len];
//查询时找到不大于当前区间长度的最大的2次幂，不难想到2的k次方>=区间的长度的一半
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

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;
}