什么是RMQ

举个例子

给你一个长度为n (n≤50000)的序列,求区间[l,r]上的最大值,怎么求?So easy,\(O(n)\)扫一遍记录最大就可以了。

可是如果有Q (Q≤50000)次询问怎么办?这肯定过不了!所以我们就要用RMQ了。既然是一个面对多次查询的算法,那么为了提高查询的效率,都是要经过较长时间的预处理,RMQ也不例外,它拥有一个时间复杂度为\(O(nlogn)\)的预处理,然后可以在\(O(1)\)的时间内查询。下面我们来举一个简单的实例:

算法原理与代码实现

假设有一个数组\(a[9]=\{0,1,9,2,6,0,8,1,7\}\)

设数组dp[i][j]表示从第i位开始向后数\(2^j\)个数中的最小值。如dp[3][2]即表示从第三位(数字2)开始数4个数中最小的一个,即2,6,0,8中的最小值,这里是0,所以dp[3][2]=0。

既然我用了dp数组来表示,那么他是有递推方程的。可以这样来想,当前\(i\)点向右数\(2^j\)个中的最大值,可以表示成【\(i\)点向右数\(2^{j-1}-1\)个中的最大值和从\(i+2^{j-1}\)向右数\(2^{j-1}\)个中的最大值】中的最大值(有点绕,仔细看)

那么我们可以轻而易举的写出dp转移方程

$$dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$$

然后就能轻而易举的写出代码:

(由于我没有找到这么裸的模板题,所以自己出一道)

题目描述:

已知一个长为n的队列,给出m次提问\(l,r\),求区间[l,r]或[r,l]上的最值。 (n≤50000,m≤100000)

输入格式:

第一行两个整数n,m,第二行n个整数表示序列,接下来m行每行两个整数表示查询区间[l,r](或[r,l])

输出格式:

m行,第i行对应问题i的答案

建议你们自己写一下跑一下这两个数据,然后实在不会再看我的程序(我都讲得这么清楚明白怎么会不会呢?)

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=50010;
int n,m;
int a[M];
int dp[M][20];

int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

void RMQ(){
	for(int i=1;i<=n;i++)
		dp[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int main(){
//	freopen("testdata1.in","r",stdin);
//	freopen("testdata1.out","w",stdout);
	n=Read(),m=Read();
	for(int i=1;i<=n;i++)
		a[i]=Read();
	RMQ();
	for(int i=1;i<=m;i++){
		int l=Read(),r=Read(),k;
		if(l==r){
			printf("%d\n",a[l]);
			continue;
		}
		if(l>r) swap(l,r); 
		for(int i=1;i<=20;i++)
			if((1<<i)>=r-l+1){
				k=i-1;
				break;
			}
		int rr=r+1-(1<<k);
		printf("%d\n",max(dp[l][k],dp[rr][k]));
	}
	return 0;
}

是不是很简单呢?

拓展:求LCA

我们在最近公共祖先LCA一文中讲到,倍增求LCA是很常见的好写的算法,其时间复杂度是\(O((n+m)logn)\),这里我们介绍的RMQ算法,则是可以以\(O(nlogn)\)的复杂度做预处理,\(O(1)\)的复杂度查询,看起来比倍增更快哦!

首先要介绍一个东西:DFS序

现在你有一个长得非常像cxk的树,这棵树的DFS序就是从根结点出发,DFS遍历是依次经过的节点的序列。比如这棵坤坤树的DFS序就是\(1,2,3,4,5,8,6,9,10,7\)或者\(1,6,7,9,10,2,4,5,8,3\)或者……,这些不同的DFS序都是对的,只不过取决于你先加入了哪条边等,但既然你用DFS序,那么他的顺序不同对答案是没有影响的!

很显然的我们可以想到DFS有一个性质,就是进入一个子树后不会再进入,因此一个子树中深度最浅的节点必定是这个子树的树根。又,我们能想到关于LCA的一个性质,就是\(LCA(a,b)\)一定是同时囊括a,b两点的一棵子树的根节点。【这里一定要想明白啊!!这里我说的“子树”是整个树的子树,意味着这里的“子树”也可以是整个树,表示节点a,b的LCA就是整个树的树根。】

所以知道了上面的两个性质,我们来思考一下LCA该如何用RMQ来求。

首先我们要来一个DFS序的加强版欧拉序(介绍我在链接里,我懒得再写一遍了),然后对欧拉序做RMQ的预处理,处理出从每一个点开始i向右数\(2^j\)个中的点的深度最小值。这就是预处理部分。

查询操作直接查询欧拉序上s[x]到s[y]区间上的深度最小的点,就是他们的LCA了!是不是很简单很神奇???

还是上一个我WA了100次的题: https://www.luogu.org/problem/SP14932
上代码:

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=2080;
bool vis[M<<1];
int n,m,q,cnt,now,rt;
int s[M<<1],deep[M<<1],el[M<<4],head[M<<1];
int dp[M<<1][20];
struct edge{
	int to,nxt;
	edge(){
		to=nxt=0;
	}
}e[M<<1];

int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Init(){
	now=cnt=0;
	memset(vis,false,sizeof(vis));
	memset(deep,0,sizeof(deep));
	memset(head,0,sizeof(head));
	memset(el,0,sizeof(el));
	memset(dp,0,sizeof(dp));
	memset(e,0,sizeof(e));
}

inline void Add(int x,int y){
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}

void DFS(int x){ 
	el[++now]=x;
	s[x]=now;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		deep[v]=deep[x]+1;
		DFS(v);
		el[++now]=x;
	}
}

void RMQ(){
	for(int i=1;i<=(n<<1);i++)
		dp[i][0]=el[i];
	for(int j=1;(1<<j)<=(n<<1);j++)
		for(int i=1;i<=(n<<1)+1-(1<<j);i++)
			dp[i][j]=deep[dp[i][j-1]]<=deep[dp[i+(1<<j-1)][j-1]]?dp[i][j-1]:dp[i+(1<<j-1)][j-1];
}

int main(){
	int T=Read();
	for(int sign=1;sign<=T;sign++){
		Init();
		n=Read();
		for(int i=1;i<=n;i++){
			m=Read();
			for(int j=1;j<=m;j++){
				int tmp=Read();
				vis[tmp]=true;
				Add(i,tmp);
			}
		}
		for(int i=1;i<=n;i++)
			if(!vis[i]){
				rt=i;
				break;
			}
		deep[rt]=1;
		DFS(rt);
		RMQ();
		q=Read();
		printf("Case %d:\n",sign);
		for(int i=1;i<=q;i++){
			int u=Read(),v=Read();
			if(u==v){
				printf("%d\n",u);
				continue;
			}
			if(s[u]>s[v]) swap(u,v);
			int k=log2(s[v]-s[u]+1);
			printf("%d\n",deep[dp[s[u]][k]]<=deep[dp[s[v]-(1<<k)+1][k]]?dp[s[u]][k]:dp[s[v]-(1<<k)+1][k]);
		}
	}
	return 0;
}

这个理论上比倍增复杂度低,但是好像跑出来我倍增20ms,这个30ms,不知道为什么。这个在写的时候还是看自己吧,觉得哪个好写就哪个!

0 0 votes
文章评分
订阅这个评论
提醒

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments