引入

现在给定一个长度为\(n\)的数组和\(m\)个询问，每次询问 \([l, r]\) 内的区间最值。\(n \leq 10^5\)。

显然，这道题可以使用 线段树 来维护区间最值，总查询时间复杂度为 \(O(qlogn)\) 。但是，当 \(q\) 较大、\(n\) 较小的时候，我们就可以使用 \(RMQ\) 来解决区间最值查询。

\(RMQ\) 使用 倍增 和 \(dp\) 思想，其预处理时间复杂度为 \(O(nlogn)\)，查询时间复杂度为 \(O(1)\)。

算法思想

设 \(dp_{i, j}\) 为从下标为 \(i\) 的元素开始，连续 \(2^j\) 个元素（包含下标为 \(i\) 的元素）中的最小值。显然，如果我们把这个区间从中间分成两部分，分别求出它的最小值 \(m_{l}\) 和 \(m_{r}\) ，则该区间的最小值等于 \(min(m_{l}, m_{r})\)

我们的状态转移方程可以由此得出：设 \(r = i + 2^j - 1\)，则区间 \([l, r]\) 的最小值等于 \(min(dp_{i, j - 1}, dp_{i + 2^{j - 1}}, r)\)

对于 \(dp_{i, 0}\)，因为 \(2^0 = 1\) ，所以我们可以认为 \(dp_{i, 0}\) 即为从 \(i\) 开始连续 \(1\) 个元素，也就是 \(i\) 本身。

这样，预处理部分就完成了。接下来回答 \(RMQ(l, r)\) 。设 \(k = \lfloor log(r - l + 1) \rfloor\)，那么 \(RMQ(l, r) = min(dp_{l, k}, dp_{r - 2^k + 1, k})\)。可以这样简单理解：因为 \(2^{k + 1} > r - l + 1\)，所以从 \(i\) 开始的 \(2 ^ k\) 个元素和从 \(r - 2^k + 1\) 开始的 \(2^k\) 个元素一定可以覆盖且仅覆盖区间 \([l, r]\)。从这两个值中取最小值就是 \(RMQ(l, r)\)。

模板

例题链接

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 100005
#define maxm 30
 
int n, m;
int a[maxn], dp[maxn][maxm]; 
 
int getLog(int x)
{
    int res = 0, num = 1;
    while (num <= x)
    {
        res++;
        num *= 2;
    }
    return res - 1;
}
 
int main()
{
    int l, r;
    int ans, k;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i][0] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &l, &r);
        k = getLog(r - l + 1);
        ans = max(dp[l][k], dp[r - (1 << k) + 1][k]);
        printf("%d\n", ans);
    }
    return 0;
}

例题选讲

最长相等子序列

例题链接

给定一个长度为 \(n\) 的序列，试求出序列中 \([l, r]\) 内最长的且所有元素相等的连续区间。

显然，我们可以维护一个最大子段和数组 \(f\) 。若 \(a_i = a_{i - 1}\) ，则 \(f_i = f_{i - 1} + 1\)，否则 \(f_i = 1\) 。对于 \([l, r]\) 中第一个连续且所有元素相等的区间 \(k\)，我们需要特殊处理，求出它的长度。设 \(k\) 的结尾为 \(x\) ，显然第二个区间及后面的最长长度可以直接用一个 \(RMQ\) 数组来维护 \(f\) 数组的最大值，直接取 \(RMQ(x + 1, r)\) 就是第二个区间及后面的最长长度。整个区间 \([l, r]\) 的解即为 第一个区间的长度和 \(RMQ(x + 1, r)\) 的最大值。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;
 
const int maxn = 1e5 + 5;
const int maxm = 20;
 
int n, q;
int a[maxn], f[maxn], dp[maxn][maxm];
 
int Log(int x)
{
    int res = 0, num = 1;
    while (num <= x)
    {
        res++;
        num *= 2;
    }
    return res - 1;
}
 
int main()
{
    int l, r, p, k, ans;
    while (scanf("%d", &n) && n)
    {
        scanf("%d", &q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if (a[i] == a[i - 1])
                f[i] = f[i - 1] + 1;
            else
                f[i] = 1;
            dp[i][0] = f[i];
        }
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d", &l, &r);
            p = l + 1;
            while (a[p] == a[p - 1] && p <= r)
                p++;
            ans = p - l;
            if (p <= r)
            {
                k = Log(r - p + 1);
                ans = max(ans, max(dp[p][k], dp[r - (1 << k) + 1][k]));
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}