Problem

题目链接

Solution

RMQ(Range Minimum / Maximum Query)问题是指给定一个数组，有很多的query，问你该数组[i,j]区间里的极大/小值是多少。

注意，该问题的难点在于很多query，因此对每一个query都进行遍历求最值的暴力算法肯定不行

对于给定数组，并不会更新数组的RMQ问题，我们可以采用ST算法来做

ST算法的具体做法就是

定义dp[i][j]为区间[i,i+2^j-1]里的极值，即从i开始的连续2 ^j个值里的极值

容易想到，当区间长度为1时，即j=0，dp[i][0]都是初始为num[i]

f [ i ][ j ] = max { f [ i ][ j - 1 ] , f [ i + ( 1 << ( j - 1 ) ) ][ j - 1 ] }

双层循环，外层枚举区间长度2^j，内层枚举起点i

因为初始化了区间长度为1的f值，那么可以由相邻的两个长度为1的区间合并出一个长度位2的区间

以此类推…

那么，我们可以通过枚举所有起点以及区间长度来计算出所有的可能性

查询区间为[l,r]，区间长度为k=r-l+1，因为j的含义是代表2^j，所以要对k取个对数

这里有个小问题，枚举的区间长度都是2的幂次方，那么如果某个query区间长度不为2的幂该怎么办呢？

对于区间[l,r]，我们只要取出从l开始的2^ k个元素和从r向左的2k个元素两者做个比较，就一定能覆盖[l,r]区间即比较f[l][k]和f[r-(1<<k)][k]

这题的数据量有点大，用快速输入才过了

//
// Created by DongChenglong on 2020/5/27.
//#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>using namespace std;const int N = 1e5 + 10;int num[N];
int stTable[N][25];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;
}void getST(int n) {for (int i = 1; i <= n; ++i) stTable[i][0] = num[i];for (int j = 1; (1 << j) <= n; ++j)for (int i = 1; i + (1 << j) - 1 <= n; ++i)stTable[i][j] = max(stTable[i][j - 1], stTable[i + (1 << (j - 1))][j - 1]);}int main() {int n, m;n = read();m = read();
//    scanf("%d %d", &n, &m);for (int i = 1; i <= n; ++i)
//        scanf("%d",&num[i]);num[i] = read();getST(n);while (m--) {int l, r;
//        scanf("%d %d",&l,&r);l = read();r = read();int k = log2(r - l + 1);printf("%d\n", max(stTable[l][k], stTable[r - (1 << k) + 1][k]));}
}

参考博客：链接