RMQ问题小结
by Wine93 2014.1.14
1.算法简介
RMQ问题可分成以下2种
(1)静态RMQ:ST算法
一旦给定序列确定后就不在更新,只查询区间最大(小)值!这类问题可以用倍增的ST算法进行预处理
预处理:O(nlogn)
查询:O(1)
(2)动态RMQ:线段树
要更新一些值,还有询问
更新:O(logn)
查询:O(logn)
2.相关题目
(1)静态RMQ
1.POJ 3264 Balanced Lineup(一维静态RMQ模板题) http://poj.org/problem?id=3264
题意:给定n(n<=50000)个数字,每次询问[l,r]内的最大值和最小值差
分析:裸的一维RMQ,用ST预处理!
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define N int log2[N];
int a[N],f[N][],g[N][]; //f:max g:min
void initRMQ(int a[],int n)
{
int i,j;
log2[]=;
for(i=;i<N;i++)
log2[i]=log2[i-]+!(i&(i-));
for(i=;i<=n;i++)
f[i][]=g[i][]=a[i];
for(j=;(<<j)<=n;j++)
for(i=;i+(<<j)-<=n;i++)
{
f[i][j]=max(f[i][j-],f[i+(<<j-)][j-]);
g[i][j]=min(g[i][j-],g[i+(<<j-)][j-]);
}
} int getmax(int l,int r)
{
int k=log2[r-l+];
return max(f[l][k],f[r-(<<k)+][k]);
} int getmin(int l,int r)
{
int k=log2[r-l+];
return min(g[l][k],g[r-(<<k)+][k]);
} int main()
{
int i,n,m,x,y;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<=n;i++)
scanf("%d",&a[i]);
initRMQ(a,n);
for(i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",getmax(x,y)-getmin(x,y));
}
}
return ;
}
POJ 3264
2.HDU 2888 Check Corners(二维静态RMQ模板题) http://acm.hdu.edu.cn/showproblem.php?pid=2888
题意:给定一个n*m (1<=m,n<=300)的矩阵!每次询问(r1，c1)为左上角,(r2,c2)为右下角的子矩形的最大值。
分析:裸的二维RMQ,用ST预处理即可!
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define N
# define M
int dp[N][N][M][M];
int log2[N];
int a[N][N],n,m,q; void initRMQ()
{
int i,j,k,l;
for(k=;(<<k)<=n&&k<=;k++)
for(l=;(<<l)<=m&&l<=;l++)
for(i=;i+(<<k)-<=n;i++)
for(j=;j+(<<l)-<=m;j++)
{
if(k==&&l==) dp[i][j][k][l]=a[i][j];
else if(k==) dp[i][j][k][l]=max(dp[i][j][k][l-],dp[i][j+(<<l-)][k][l-]);
else if(l==) dp[i][j][k][l]=max(dp[i][j][k-][l],dp[i+(<<k-)][j][k-][l]);
else
{
int a=max(dp[i][j][k-][l-],dp[i][j+(<<l-)][k-][l-]);
int b=max(dp[i+(<<k-)][j][k-][l-],dp[i+(<<k-)][j+(<<l-)][k-][l-]);
dp[i][j][k][l]=max(a,b);
}
}
} int getmax(int x1,int y1,int x2,int y2)
{
int k=log2[x2-x1+];
int l=log2[y2-y1+];
int a=max(dp[x1][y1][k][l],dp[x2-(<<k)+][y1][k][l]);
int b=max(dp[x1][y2-(<<l)+][k][l],dp[x2-(<<k)+][y2-(<<l)+][k][l]);
return max(a,b);
} int main()
{
int i,j,x1,y1,x2,y2;
log2[]=;
for(i=;i<N;i++)
log2[i]=log2[i-]+!((i-)&i);
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%d",&a[i][j]);
initRMQ();
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=getmax(x1,y1,x2,y2);
int res=max(max(a[x1][y1],a[x1][y2]),max(a[x2][y1],a[x2][y2]));
printf("%d ",ans);
if(res==ans) printf("yes\n");
else printf("no\n");
}
}
return ;
}
HDU 2888
3.LightOJ 1081 Square Queries(二维静态RMQ降维) http://www.lightoj.com/volume_showproblem.php?problem=1081
题意:给定一个n*n(n<=500)的矩阵!每次询问以(x,y)为左上角,边长为l的正方形区域内的最大值
分析:如果用一般的二维RMQ预处理,时间复杂度为n*n*logn*logn(约2000万),会超时!因为查询区域为正方形,我们只要每次都存储正方形就行了!
Max[i][j][k]:以(i,j)为左上角,边长为2^k区域内的最大值,每次倍增把大正方形拆成4个小正方形即可!
# include<map>
# include<set>
# include<cmath>
# include<queue>
# include<stack>
# include<vector>
# include<string>
# include<cstdio>
# include<cstring>
# include<iostream>
# include<algorithm>
# include<functional>
using namespace std; typedef pair<int,int> PII;
# define MOD
# define LL long long
# define pb push_back
# define F first
# define S second
# define N
# define M
int Max[N][N][M],Log2[N];
int a[N][N]; void initLog() //初始化Log2数组
{
int i;
Log2[]=-;
for(i=;i<N;i++)
Log2[i]=Log2[i-]+!(i&i-);
} void initRMQ(int n)
{
int i,j,k,lu,ld,ru,rd;
for(k=;(<<k)<=n;k++)
for(i=;i+(<<k)-<=n;i++)
for(j=;j+(<<k)-<=n;j++)
{
if(k==) Max[i][j][k]=a[i][j];
else
{
lu=Max[i][j][k-]; //左上角
ld=Max[i+(<<k-)][j][k-]; //左下角
ru=Max[i][j+(<<k-)][k-]; //右上角
rd=Max[i+(<<k-)][j+(<<k-)][k-]; //右下角
Max[i][j][k]=max(max(lu,ld),max(ru,rd));
}
}
} int Query(int x,int y,int l)
{
if(l==) return a[x][y]; //注意
int k=Log2[l];
int lu=Max[x][y][k];
int ld=Max[x+l-(<<k)][y][k];
int ru=Max[x][y+l-(<<k)][k];
int rd=Max[x+l-(<<k)][y+l-(<<k)][k];
return max(max(lu,ld),max(ru,rd));
} int main()
{
//freopen("in.txt","r",stdin);
initLog();
int cas,T,i,j,n,m,x,y,l;
scanf("%d",&T);
for(cas=;cas<=T;cas++)
{
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&a[i][j]);
initRMQ(n);
printf("Case %d:\n",cas);
while(m--)
{
scanf("%d%d%d",&x,&y,&l);
printf("%d\n",Query(x,y,l));
}
}
return ;
}
Lightoj 1081
4.POJ 3368 Frequent values
题意:给定n(n<=100000)个数,每次询问一个区间内重复数字的最大次数
5.POJ 2452 Sticks Problem
6.HDU 3486 Interviewe
(2)动态RMQ
1.HDU 1754 I Hate It (一维动态RMQ模板题)
2.Uva 11297 Census(二维动态RMQ模板题)
3.HDU 4819 Mosaic (13年长春现场)
4.NBU 2475 Survivors
5.BUAA 724 晴天小猪的神题