RMQ(Range Minimum/Maximum Query)问题是求区间最值问题，用ST算法，可以做到O(nlogn)的预处理，O(1)地回答每个询问。
以求最大值为例，设f[i,j]表示以i为起点，长度为2^j这个区间中的最大值，即[i,i+2^j-1]这个区间内的最大值，那么在询问[a,b]区间的最大值时答案就是max(f[a,k], f[b-2^k+1,k]),其中k是满足2^k<=b-a的最大的k，即k=ln(b-a+1)/ln(2);另外,这两个区间必须覆盖[a,b].
f的求法可以用动态规划，f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]).
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3264
#include<iostream>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int n,q,a,b;
int h[50005];
int maxn[50005][16];
int minn[50005][16];
void st_init()
{
for(int i=1;i<=n;i++)
maxn[i][0]=minn[i][0]=h[i];
int m=int(log(double(n))/log(2.0));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
maxn[j][i]=maxn[j][i-1];
if(j+(1<<(i-1))<=n)
maxn[j][i]=max(maxn[j][i],maxn[j+(1<<(i-1))][i-1]);
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
minn[j][i]=minn[j][i-1];
if(j+(1<<(i-1))<=n)
minn[j][i]=min(minn[j][i],minn[j+(1<<(i-1))][i-1]);
}
}
int st_search(int l,int r)
{
int m=int(log(double(r-l+1))/log(2.0));
int mx=max(maxn[l][m],maxn[r-(1<<m)+1][m]);
int mn=min(minn[l][m],minn[r-(1<<m)+1][m]);
return mx-mn;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
st_init();
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",st_search(a,b));
}
//system("pause");
return 0;
}
posted on 2010-08-28 13:29
wuxu 阅读(202)
评论(0) 编辑 收藏 引用 所属分类:
动态规划