RMQ问题
RMQ(Range Minimum/Maximum Query)问题是指多次查询某个范围内的最大最小值(或极值),比如对一个序列多次查询区间的最大最小值。
设范围内共有 \(n\) 个元素,查询 \(m\) 次。
朴素算法:
遍历所有范围内的元素,再取最大或最小,则单次查询时间复杂度最
坏为 \(O(n)\),总时间复杂度最坏为:\(O(nm)\),还是太慢了。
于是就有无数的牛人发明了各种用于 RMQ 问题算法,并且有些算法是可以做到区间修改的,下面这张表格看一下:
算法 | 预处理 | 单次查询 | 单点修改 | 区间修改 |
---|---|---|---|---|
朴素算法 | 无 | \(O(n)\) | \(O(1)\) | \(O(n)\) |
分块 | \(O(n)\) | \(O(\sqrt{n})\) | \(O(\sqrt{n})\) | \(O(\sqrt{n})\) |
线段树 | \(O(n)\) | \(O(\log{n})\) | \(O(\log{n})\) | \(O(\log{n})\) |
树状数组 | \(O(n)\) | \(O(\log{n})\) | \(O(\log{n})\) | 结合差分可以做到 \(O(\log{n})\) |
ST 表 | \(O(n \log n)\) | \(O(1)\) | 不支持 | 不支持 |
不难看出,线段树从综合上来看是更厉害的,不过如果只有 RMQ, 那么 ST 表是最厉害的。
ST 表
思想
我们设这个序列是 \(a_1,a_2,a_3,...,a_n\)。
我们可以预处理出所有长度为 \(2^i\) 的长度的区间的答案,比如对于一个长度为 \(10\) 的区间,我们需要预处理出下图所有彩色区间的最大值:
其中橙色的区间是所有长度为 \(2\) 的区间,蓝色是所有长度为 \(4\) 的区间,绿色是所有长度为 \(8\) 的区间。
我们设 \(st_{i,j}\) 为以 \(i\) 开头,长度为 \(2^j\) 的区间的最大值,于是在上图中我们发现,两个相邻的橙色区间可以合并成一个蓝色区间,两个相邻的蓝色区间可以合并成一个绿色区间,于是我们就得到了 \(st_{i,j}\) 的递推式:
\[st_{i,0}=a_i \]\[st_{i,j}=\max\{st_{i,j-1}, st_{i+2^{j-1},j-1}\} \]这样的预处理时间和空间复杂度都是 \(O(n \log n)\) 的,因为总共有 \(n \log n\) 个需要预处理的区间。
所以我们费了这么大劲搞出来一个东西有什么用呢?ST 表可以做到 \(O(1)\) 查询。
举个例子,假设我们要查询第 3 到 8 这段区间的最大值,那么我们需要两个长度不比 \((8-3+1)=6\) 大中最大的 2 的幂,且这两个区间能覆盖 \([3,8]\)。如下图:
黑色区间就是我们选择的区间,长度为 \(4\),其实就是 \(2^{\lfloor \log_2(8-3+1)\rfloor}=2^{\lfloor \log_2(6)\rfloor}=2^2\) ,于是对于区间 \([l,r]\) 来说,我们设 \(k = \lfloor \log_2(r-l+1)\rfloor\), 答案就是:\(\max\{st_{l,k}, st_{r-2^k+1,k}\}\),这样查询就是 \(O(1)\) 的了。
实现
预处理
我们设 \(pw_i=2^i\),\(lg_i=\lfloor \log_2(i)\rfloor\),于是我们就可以写出预处理代码:
void init() {
lg[1] = 0, pw[0] = 1;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= 20; i++)
pw[i] = pw[i - 1] * 2;
for (int i = 1; i <= n; i++)
st[i][0] = a[i];
for (int j = 1; pw[j] <= n; j++)
for (int i = 1; i + pw[j] - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + pw[j - 1]][j - 1]);
}
查询
按照我们之前说过的方法直接查询即可:
int qry(int l, int r) {
int k = lg[r - l + 1];
return max(st[l][k], st[r - pw[k] + 1][k]);
}
一些题目
题目名 【模板】ST 表
题目链接:【模板】ST 表
思路:
模板题,放一下代码。
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXN_LOG = 20;
int st[MAXN][MAXN_LOG] = {{0}};
int a[MAXN] = {0}, lg[MAXN] = {0}, pw[MAXN_LOG] = {0}, n, m;
void init() {
lg[1] = 0, pw[0] = 1;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
for (int i = 1; i <= 20; i++)
pw[i] = pw[i - 1] * 2;
for (int i = 1; i <= n; i++)
st[i][0] = a[i];
for (int j = 1; pw[j] <= n; j++)
for (int i = 1; i + pw[j] - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + pw[j - 1]][j - 1]);
}
int qry(int l, int r) {
int k = lg[r - l + 1];
return max(st[l][k], st[r - pw[k] + 1][k]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
init();
for (int i = 1, l, r; i <= m; i++) {
scanf("%d%d", &l, &r);
printf("%d\n", qry(l, r));
}
return 0;
}
[USACO07JAN] Balanced Lineup G
题目链接:[USACO07JAN] Balanced Lineup G
思路:
挺没意思的一道题,记录最大和最小值即可。
代码:提交记录
gcd区间
题目链接:gcd区间
思路:
我们可以把去 ST 表中取最大的操作改成取 \(\gcd\),这样就可以过了。
代码:提交记录
玉米地
题目链接:玉米地
思路:
这里涉及到二维 ST 表。
ST 表也可以是二维的,我们设 \(st_{i,j,k}\) 表示左上角位置为 \((i,j)\) ,边长为 \(2^k\) 的正方形中的最大值(最小值同理,最后相减即可,这里只说最大值),对于 \(st_{i,j,k}\),我们可以这样更新:
\[st_{i,j,k}=\max\{ st_{i,j,k-1}, st_{i,j+2^k,k}, st_{i+2^k,j,k}, st_{i+2^k,j+2^k,k}\} \]我们通过这张图直观感受一下:
这就是初始化,这样的时间复杂度是 \(O(n^2\log n)\)。
查询操作大同小异,我们依然是找到不比边长大中最大的 2 的幂。设我们要找左上角为 \((i,j)\),边长为 \(len\) 的正方形中的最大值,我们设 \(k=\lfloor \log_2(len)\rfloor\),答案就是:
\[\max\{ st_{i,j,k}, st_{i,j+len-2^k,k}, st_{i+len-2^k,j,k}, st_{i+len-2^k,j+len-2^k,k}\} \]再来一张图直观感受一下:
其实只要有图就好理解了,于是我们就掌握了二维 ST 表。
但这道题有个问题,询问有可能出界,于是我们预处理是直接把边长乘 2,然后把所有不在界里的都设成无穷大或无穷小即可。
代码:提交记录
[JSOI2008] 最大数
题目链接:[JSOI2008] 最大数
思路:
这道题如果不强制在线,我们完全可以离线,等所有数都加完了再去处理询问,但是这道题强制在线,所以我们需要想办法让 ST 表支持修改。
我们发现,如果在末尾新增一个元素,那么所有长度为 2 的幂次方,且末尾为这个元素的都需要更新。但这是新的末尾,所以其实我们之前并没有记录过以上区间的答案,于是我们可以通过查询直接记录即可。由于最多只需要更新 \(\log(n)\) 个区间,所以修改是 \(O(\log n)\),查询是 \(O(1)\) 的。
具体怎么更新,我们假设新的末尾是第 \(n\) 个元素,那么对于某个 \(k\) 满足 \(2^k \le n\),\(st_{n-2^k+1,k}=\max\{\max\limits_{n-2^k+1\le i\le n-1}\{a_i\},a_n\}\),而 \(\max\limits_{n-2^k+1\le i\le n-1}\{a_i\}\) 可以 \(O(1)\) 算出来,于是更新一个值也是 \(O(1)\) 的。
代码:提交记录
FREQUENT - Frequent values
题目链接:FREQUENT - Frequent values
思路:
一道有趣的题目,首先我们要求的依然是极值,所以依然可以用 ST 表,不过我们这次需要对预处理的区间记录以下几个信息:
\(ans\):这段区间的答案。
\(pre\):这段区间所有数都相同的最长前缀长度。
\(suf\):这段区间所有数都相同的最长后缀长度。
\(l\):这段区间的左端点。
\(r\):这段区间的右端点。
\(len\):这段区间的长度。(其实通过 \(l,r\) 也能直接推出来)
初始化时,把相邻的且长度相同的两个区间合并成一个时,设小区间叫 \(x\) 和 \(y\),则大区间应该这么变:
-
大区间的 \(l=x.l,r=x.r,len=x.len+y.len\)。
-
若 \(a_{x.r}=a_{y.l}\),则 \(ans=\max\{x.ans,y.ans,x.suf+y.pre\}\);
否则 \(ans = \max\{x.ans,y.ans\}\).。 -
若 \(a_{x.l}=a_{y.l}\),则 \(pre=x.len+y.pre\);否则 \(pre=x.pre\)。
-
若 \(a_{x.r}=a_{y.r}\),则 \(suf=y.len+x.suf\);否则 \(suf=y.suf\)。
这样依然可以在 \(O(n \log n)\) 的时间里完成预处理。
考虑查询时,我们还是设 \(k=\lfloor \log_2(r-l+1)\rfloor\),然后分以下两种情况讨论:
-
若重叠部分的数全部相同,那么答案就是 \(\max\{st_{l,k}.ans,st_{r-2^k+1,k}.ans,[{st_{l,k}.suf+st_{r-2^k+1,k}.pre-2^{k+1}+(r-l+1)}]\}\)
-
否则答案是:\(\max\{st_{l,k}.ans,st_{r-2^k+1,k}.ans\}\)
代码:提交记录
Strip
题目链接:Strip
思路:
这道题很有意思,我们一步一步来。
首先这道题很明显时不能贪心的,于是我们考虑动态规划。我们设 \(dp_i\) 表示前 \(i\) 个元素能分成的最小段数,那么最朴素的更新就是枚举最后选的一段,我们可以用 ST 表 \(O(1)\) 查询极差判断是否能选,于是就有:
\[dp_i=\min\{dp_j+1\}(1 \le j < i,i - j \ge L,\max_{j < k\le i}{a_k}-\min_{j<k\le i}{a_k} \le s) \]但这样是 \(O(n^2)\) 的,考虑如何优化。
我们发现,当一个区间越来越长,极差单调不降。原因很简单,因为最大值不会变小,最小值不会变大,而极差等于最大值减最小值,于是极差单调不降。
这个有什么好处呢?这就意味着以 \(i\) 结尾的那一段的长度大于等于 \(L\),同时也会小于等于某个数,因为极差有上限。所以我们要找到 \(i\) 之前第一个使得以 \(i\) 结尾的段极差小于等于 \(s\) 的。举个列子,像下图这样:
Dif 就是极差的意思,在上图中,真正能去影响 \(dp_i\) 的是 \(dp_{i-2}\) 到 \(dp_{i-4}\),\(dp_{i-1}\) 长度不够,\(dp_{i-5}\) 往前极差太大,所以:
\[dp_i=\min\{dp_{i-2},dp_{i-3},dp_{i-4}\}+1 \]一般化,我们设 \(cur\) 为能影响 \(dp_i\) 的下标中最小的一个,那么其实 \(dp_i\) 就是 \(\min\limits_{cur \le j\le i-L}\{dp_j\} +1\)。
我们进一步发现对于每个 \(i\) 来说,\(cur\) 也是不降的,于是我们可以搞一个指针指向 \(cur\),每次向右移动,最多移动 \(n\) 次,所以时间复杂度是 \(O(n)\) 的。
再考虑如何求 \(\min\limits_{cur \le j\le i-L}\{dp_j\}\),这不就是一个 RMQ 吗?而且每次我们会往 \(dp\) 数组末尾加一个元素,而 ST 表刚好支持 \(O(\log n)\) 的末尾添加元素,所以我们在搞一个维护 \(dp\) 数组最小值的 ST 表即可。
这道题大致思路就是这样,最终时间复杂度是 \(O(n \log n)\) 的。不过实现是还是有很多细节需要注意。
代码:提交记录
Friends and Subsequences
思路:
这道题也是很有意思的一道题。首先朴素的做法肯定是枚举区间,然后用 ST 表进行 \(O(1)\) 判断。但是复杂度是 \(O(n^2)\) 的。
我们首先要想到固定一个边界。即,我们去枚举所有 \(l\),尝试去用 \(O(\log n)\) 的时间复杂度算出有多少 \(r\) 满足题目的限制。我们拿个序列研究一下,当 \(n=6\),\(a=1,2,3,2,1,4;b=6,7,3,3,1,2\), 以 \(l=1\) 时为例:
其中相差指的是 \(\max\limits_{i=l}^ra_i-\min\limits_{i=l}^rb_i\) 的值,不难发现,这个值时单调不降的,于是这就促使我们可以去二分这个值等于 0 使得最小的 \(r\) 和 最大的 \(r\),他们之间(包括自己)各自与 \(l\) 组成的区间都是满足条件的区间,于是这道题我们就可以在 \(O(n \log n)\) 的时间复杂度内求出来了。
代码:提交记录
标签:log,max,笔记,st,学习,区间,ST,dp From: https://www.cnblogs.com/rlc202204/p/17009458.html