此博客停更

啊，真是太惨了，刚刚做一道RMQ模板题，发现我以前打的倍增模板是错的，于是我就水一下RMQ的倍增算法。。。全当复习

RMQ(区间最值问题)，给出一列数，有Q个询问，每次询问 l~r 之间的最小值。

显然，每次暴力循环找最小值是不够快的，所以需要一个算法或数据结构实现快速查询区间最值。

JB:"国际惯例，先放题目"

poj3264-Balanced Lineup

题目描述:有N头牛，第i头牛高度为Hi。有Q个询问，第A头牛到第B头牛之间最大高度与最小高度的差。

暴力显然是跑不过去的，所以引进RMQ的倍增算法(Sparse-Table)，它可以实现预处理O(nlogn)，查询O(1)，而且这个算法很好写。

mn[i][j]表示从i开始，长度为2^j的一段元素中的最小值，则可以mn[i][j]可以用递推的方式计算：mn[i][j]=min(mn[i][j-1] , mn[i+2^(j-1)][j-1])

要注意2^j≤n，所以mn数组元素个数不超过nlogn，代码如下：

void rmq_init(){
	int i,j,t;
	for(j=1;j<=n;j++)mn[j][0]=h[j];
	int m=floor(log((double)n)/log(2.0));
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			t=j+(1<<(i-1));
			if(t<=n)mn[j][i]=min(mn[j][i-1],mn[t][i-1]);
			else mn[j][i]=mn[j][i-1];
		}
	}
}

其中第一个for循环中i<=m与(1<<i)<=n等价

题目中要求的是输出区间最大值与最小值的差，所以就是区间最大值-区间最小值，最大值的求法类似。

好了，现在mn数组已经预处理好了，那怎么查询呢，其实很简单，令m为满足2^m≤R-L+1的最大整数，则以L开头、以R结尾的两个长度为2^m的区间合起来就覆盖了查询区域[L,R]。

查询代码如下：

int rmq(int l,int r){
	int m=floor(log((double)(r-l+1))/log(2.0));
	return min(mn[l][m],mn[r-(1<<m)+1][m]);	
}

至此，上面那题已经解决了，给出代码就当存个模板。。

#include<cstring>
#include<cmath>
#include<cstdio>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

using namespace std;

const int maxn=50001;
int h[maxn];
int mx[maxn][16],mn[maxn][16];
int n,q;

inline int read()
{
    char ch;int a=0;bool f=false;
    ch=getchar();while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
    if(ch!='-')a*=10,a+=ch-'0';else f=true;
    while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
    if(f)a=-a;
    return a;
}

void rmq_init(){
	int i,j,t;
	for(j=1;j<=n;j++) mx[j][0]=mn[j][0]=h[j];
	int m=floor(log((double)n)/log(2.0));
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
            t=j+(1<<(i-1));
			if(t<=n)mx[j][i]=max(mx[j][i-1],mx[t][i-1]);
			else mx[j][i]=mx[j][i-1];
		}
    }
    for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
            t=j+(1<<(i-1));
			if(t<=n)mn[j][i]=min(mn[j][i-1],mn[t][i-1]);
			else mn[j][i]=mn[j][i-1];
		}
	}
}

int rmq(int l,int r){
	int m=floor(log((double)(r-l+1))/log(2.0));
    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
	int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
    return a-b;
}

int main(){
//	freopen("lineup.in","r",stdin);
//	freopen("lineup.out","w",stdout);

	int i,l,r;
	n=read(),q=read();
	for(i=1;i<=n;i++)h[i]=read();
	rmq_init();
	for(i=0;i<q;i++){
		l=read(),r=read();
		printf("%d\n",rmq(l,r));
	}
}

loading...