博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【学习笔记】RMQ标准算法
阅读量:333 次
发布时间:2019-03-04

本文共 8821 字,大约阅读时间需要 29 分钟。

0.概述

R M Q ( R a n g e    M i n i m u m / M a x i m u m    Q u e r y ) RMQ (Range \;Minimum/Maximum\;Query) RMQ(RangeMinimum/MaximumQuery) 问题是指:对于长度为 n n n 的数列 A A A ,回答若干询问 R M Q ( A , i , j ) ( 1 ≤ i ≤ j ≤ n ) RMQ(A,i,j)(1\le i\le j\le n) RMQ(A,i,j)(1ijn) ,返回数列 A A A 中下标在 [ i , j ] [i,j] [i,j] 里的最小(大)值,也就是说, R M Q RMQ RMQ 问题是指求区间最值的问题。

所以我们要用 O ( n ) \mathcal O(n) O(n) 的时间预处理、 O ( 1 ) \mathcal O(1) O(1) 的时间在线查询(不支持修改)!

1. S T \tt ST ST

f ( i , j ) f(i,j) f(i,j) 表示 [ i , i + 2 j ) [i,i+2^j) [i,i+2j) 中的最小值,很明显有 f ( i , j + 1 ) = min ⁡ [ f ( i , j ) , f ( i + 2 j , j ) ] f(i,j+1)=\min[f(i,j),f(i+2^j,j)] f(i,j+1)=min[f(i,j),f(i+2j,j)]

所以这是一个 O ( n log ⁡ n ) \mathcal O(n\log n) O(nlogn) 的递推,预处理 ⌊ log ⁡ x ⌋ ( x ≤ n ) \lfloor\log x\rfloor(x\le n) logx(xn) 之后便可以做到 O ( 1 ) \mathcal O(1) O(1) 查询了。

温馨提示:这一部分是略讲的,因为大家平时都使用这种方法,RMQ标准算法 纯粹是作为一种学习罢了,在比赛中很难有时间打。

namespace STtable{
// ST表 const int MaxN = 363640, LogN = 19; int st[MaxN][LogN], duishu[MaxN], item[MaxN]; void init(const int shuzu[],int n){
for(int i=0; i<=n; ++i) st[i][0] = i, item[i] = shuzu[i]; for(int j=1; (1<
<=n; ++j) for(int i=0; i+(1<
<=n; ++i){
int &x = st[i][j] = st[i][j-1]; const int &y = st[i+(1<
>1)][j-1]; if(item[y] < item[x]) x = y; } for(int i=2; i<=n+1; ++i) duishu[i] = duishu[i>>1]+1; } int query(int l,int r){
if(l > r) swap(l,r); int k = duishu[r-l+1]; const int &x = st[l][k]; const int &y = st[r-(1<

2.约束 R M Q \tt RMQ RMQ

所谓约束 R M Q \tt RMQ RMQ 即是,对于欲查询的数列 A A A ∀ i ∈ [ 1 , n ) , A i − A i + 1 ∈ { 1 , − 1 } \forall i\in[1,n),A_{i}-A_{i+1}\in\{1,-1\} i[1,n),AiAi+1{

1,1}

其实,更广泛的,只要相邻两数之差(前者减后者)只能是两种值,都可以叫 约束RMQ

怎么做呢?分块。设定块的大小为 m = ⌊ log ⁡ n 2 ⌋ m=\lfloor\frac{\log n}{2}\rfloor m=2logn ,对于每一个块,可以求出最小值,然后将一块作为最小单位,利用 ST表 进行预处理。此处的复杂度是 O [ n m log ⁡ ( n m ) ] = O [ n log ⁡ n ( log ⁡ n − log ⁡ m ) ] = O ( n ) \mathcal O[\frac{n}{m}\log(\frac{n}{m})]=\mathcal O[\frac{n}{\log n}(\log n-\log m)]=\mathcal O(n) O[mnlog(mn)]=O[lognn(lognlogm)]=O(n) 的。

对于某一块中的“边角料”,如何处理?注意到某一块中的 差分数组 的不同的数量只有 O ( 2 m ) = O ( 2 log ⁡ n 2 ) = O ( 2 log ⁡ n ) = O ( n ) \mathcal O(2^m)=\mathcal O(2^{\frac{\log n}{2}})=\mathcal O(\sqrt{2^{\log n}})=\mathcal O(\sqrt n) O(2m)=O(22logn)=O(2logn )=O(n ) ,所以枚举它,然后处理 每一个子区间。复杂度 O ( m 2 n ) = O ( n log ⁡ 2 n ) ≤ O ( n ) \mathcal O(m^2\sqrt n)=\mathcal O(\sqrt n\log^2n)\le \mathcal O(n) O(m2n )=O(n log2n)O(n)

然后就可以 O ( 1 ) \mathcal O(1) O(1) 查询了。

namespace narrowRMQ{
// 约束RMQ const int MaxN = 4000000, block = 11; int benzhi[1<
>r&1) ++ now; else if((-- now) < all) id = r, all = now; benzhi[S][l][r] = id; } } for(int i=0; i<=n/block; ++i) data[i] = infty; for(int i=1; i<=n; ++i) if(item[i] < data[i/block]){
data[i/block] = item[i]; best[i/block] = i; } STtable::init(data,n/block); } int query(int a,int b){
if(a > b) swap(a,b); if(a == b) return a; int l = a/block; a -= l*block; int r = b/block; b -= r*block; int L = inside[l], R = inside[r]; if(l == r) return benzhi[L][a+1][b]+l*block; int res = 0, x = 0; if(l+1 <= r-1){
x = STtable::query(l+1,r-1); if(data[x] < item[res]) res = best[x]; } x = a+l*block; if(a != block-1) x = benzhi[L][a+1][block-1]+l*block; if(item[x] < item[res]) res = x; x = b+r*block; if(b != 0) x = benzhi[R][1][b]+r*block; if(item[x] < item[res]) res = x; return res; }}

3.笛卡尔树

笛卡尔树是一棵二叉树,包含了一个序列中的每个元素。对于每个元素在原序列中的下标来说,笛卡尔树是一棵二叉搜索树(即,中序遍历结果单调递增);对于每个元素的大小来说,笛卡尔树是类似于堆的(子树中的最值恰好为子树的根)。

笛卡尔树的建树过程是 O ( n ) \mathcal O(n) O(n) 的。利用笛卡尔树,在原序列上的 R M Q \tt RMQ RMQ 问题 等价于笛卡尔树上的 l c a lca lca 问题。因为 l c a lca lca 恰好为最小值——这是由定义决定的。

namespace Descartes{
// 笛卡尔树 const int MaxN = 2000000; int son[MaxN|1][2], meet[MaxN<<1]; int depth[MaxN<<1], dfn; int first[MaxN|1]; void dfs(int o,int deep=0){
meet[++ dfn] = o, depth[dfn] = deep; first[o] = dfn; // 第一次见面 for(int i=0; i<2; ++i) if(son[o][i]){
dfs(son[o][i],deep+1); meet[++ dfn] = o, depth[dfn] = deep; } } void init(int shuzu[],int n){
static vector
v; v.clear(); v.push_back(0), shuzu[0] = -infty; for(int i=1,x=0; i<=n; v.push_back(i++)){
for(x=0; shuzu[v.back()]>shuzu[i]; ) x = v.back(), v.pop_back(); son[i][0] = x, son[v.back()][1] = i; } dfn = 0, dfs(son[0][1]); }}

4. R M Q \tt RMQ RMQ l c a lca lca

l c a lca lca 有一种广为人知的求解方法:对树进行一次 d f s \tt{dfs} dfs ,在进入一个点、回溯到一个点的时候,都将这个点加入“访问序列”中。在 x x x 第一次出现于访问序列中之后,在 y y y 第一次出现于访问序列中之前, l c a lca lca 会出现,并且没有比它深度更小的点。所以只需要在 “访问序列” 中找深度最小的点即可!不就是 R M Q \tt RMQ RMQ 吗?更棒的是,它是 约束RMQ

这个转化过程显然是 O ( n ) \mathcal O(n) O(n) 的,并且得到的访问序列也是 O ( n ) \mathcal O(n) O(n) 的。

namespace normalRMQ{
void init(int shuzu[],int n){
Descartes::init(shuzu,n); narrowRMQ::init(Descartes::depth,Descartes::dfn); } int query(int l,int r){
l = Descartes::first[l], r = Descartes::first[r]; return Descartes::meet[narrowRMQ::query(l,r)]; }}

5.例题

本来是单调队列的板题(你懂的)。

一时兴起,给你们看一个很有意思,但是复杂度没有保证的,也许复杂度在这道题里是有保证的,但是在一般的题目中,它的一次查询甚至可以达到 O ( log ⁡ 2 n ) \mathcal O(\log^2 n) O(log2n)

#include 
#include
#include
#include
using namespace std;inline int readint() {
int a = 0; char c = getchar(), f = 1; for(; c<'0' or c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c and c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f;}void writeint(int x){
if(x < 0) putchar('-'), x = -x; if(x > 9) writeint(x/10); putchar((x%10)^48);}# define MB template < typename T >MB void getMax(T &a,const T &b){
if(a < b) a = b; }MB void getMin(T &a,const T &b){
if(b < a) a = b; }const int infty = (1<<30)-1;namespace STtable{
// ST表 const int MaxN = 363640, LogN = 19; int st[MaxN][LogN], duishu[MaxN], item[MaxN]; void init(const int shuzu[],int n){
for(int i=0; i<=n; ++i) st[i][0] = i, item[i] = shuzu[i]; for(int j=1; (1<
<=n; ++j) for(int i=0; i+(1<
<=n; ++i){ int &x = st[i][j] = st[i][j-1]; const int &y = st[i+(1<
>1)][j-1]; if(item[y] < item[x]) x = y; } for(int i=2; i<=n+1; ++i) duishu[i] = duishu[i>>1]+1; } int query(int l,int r){ if(l > r) swap(l,r); int k = duishu[r-l+1]; const int &x = st[l][k]; const int &y = st[r-(1<
>r&1) ++ now; else if((-- now) < all) id = r, all = now; benzhi[S][l][r] = id; } } for(int i=0; i<=n/block; ++i) data[i] = infty; for(int i=1; i<=n; ++i) if(item[i] < data[i/block]){ data[i/block] = item[i]; best[i/block] = i; } STtable::init(data,n/block); } int query(int a,int b){ if(a > b) swap(a,b); if(a == b) return a; int l = a/block; a -= l*block; int r = b/block; b -= r*block; int L = inside[l], R = inside[r]; if(l == r) return benzhi[L][a+1][b]+l*block; int res = 0, x = 0; if(l+1 <= r-1){ x = STtable::query(l+1,r-1); if(data[x] < item[res]) res = best[x]; } x = a+l*block; if(a != block-1) x = benzhi[L][a+1][block-1]+l*block; if(item[x] < item[res]) res = x; x = b+r*block; if(b != 0) x = benzhi[R][1][b]+r*block; if(item[x] < item[res]) res = x; return res; }}namespace Descartes{ // 笛卡尔树 const int MaxN = 2000000; int son[MaxN|1][2], meet[MaxN<<1]; int depth[MaxN<<1], dfn; int first[MaxN|1]; void dfs(int o,int deep=0){ meet[++ dfn] = o, depth[dfn] = deep; first[o] = dfn; // 第一次见面 for(int i=0; i<2; ++i) if(son[o][i]){ dfs(son[o][i],deep+1); meet[++ dfn] = o, depth[dfn] = deep; } } void init(int shuzu[],int n){ static vector
v; v.clear(); v.push_back(0), shuzu[0] = -infty; for(int i=1,x=0; i<=n; v.push_back(i++)){ for(x=0; shuzu[v.back()]>shuzu[i]; ) x = v.back(), v.pop_back(); son[i][0] = x, son[v.back()][1] = i; } dfn = 0, dfs(son[0][1]); }}namespace normalRMQ{ void init(int shuzu[],int n){ Descartes::init(shuzu,n); narrowRMQ::init(Descartes::depth,Descartes::dfn); } int query(int l,int r){ l = Descartes::first[l], r = Descartes::first[r]; return Descartes::meet[narrowRMQ::query(l,r)]; }}const int MaxN = 2000001;int a[MaxN], n, m;int main(){ // freopen("rmq.in","r",stdin); // freopen("rmq.out","w",stdout); n = readint(), m = readint(); for(int i=1; i<=n; ++i) a[i] = readint(); normalRMQ::init(a,n); putchar('0'), putchar('\n'); for(int i=2; i<=n; ++i){ int j = max(1,i-m); j = normalRMQ::query(j,i-1); writeint(a[j]), putchar('\n'); } return 0;}

6.链接

竟然 把这个问题讲清楚了的,点名表扬!

还有,感觉是从 j a v a java java 转行的?

7.吐槽

是不是我的道行 [ h e ˊ n g ] [héng] [heˊng] 太浅,见的太少?但是我确实没有在 C++ \text{C++} C++ 中找到能够精确对应这一段 j a v a java java 代码的:

abstract class class_name{
private static boolean[] some_data; public static final void method_name(){
// do something ... }}

抽象的目的是使其不能被实例化,仅成员方法被调用(且不能够被重写)。

虽然 C++ \text{C++} C++ 中给出了 namespace \text{namespace} namespace ,实现了无法实例化、不能重写,但是默认 p u b l i c public public 了!肿么办?

如果用纯虚函数 virtual void method() = 0 ,子类可以将其补充完整啊……

总的来说,就是 C++ \text{C++} C++ 没有 f i n a l final final 的修饰,不能阻止子类的重写。令人头疼!

当然咯,这些话并不代表着两种编程语言的优劣,只是我这个小蒟蒻自己吐槽一下而已。

转载地址:http://xgvq.baihongyu.com/

你可能感兴趣的文章