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 50005 int log2[N]; int a[N],f[N][20],g[N][20]; //f:max g:min void initRMQ(int a[],int n) { int i,j; log2[1]=0; for(i=2;i<N;i++) log2[i]=log2[i-1]+!(i&(i-1)); for(i=1;i<=n;i++) f[i][0]=g[i][0]=a[i]; for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) { f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]); } } int getmax(int l,int r) { int k=log2[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]); } int getmin(int l,int r) { int k=log2[r-l+1]; return min(g[l][k],g[r-(1<<k)+1][k]); } int main() { int i,n,m,x,y; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); initRMQ(a,n); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",getmax(x,y)-getmin(x,y)); } } return 0; }
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 302 # define M 9 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=0;(1<<k)<=n&&k<=8;k++) for(l=0;(1<<l)<=m&&l<=8;l++) for(i=1;i+(1<<k)-1<=n;i++) for(j=1;j+(1<<l)-1<=m;j++) { if(k==0&&l==0) dp[i][j][k][l]=a[i][j]; else if(k==0) dp[i][j][k][l]=max(dp[i][j][k][l-1],dp[i][j+(1<<l-1)][k][l-1]); else if(l==0) dp[i][j][k][l]=max(dp[i][j][k-1][l],dp[i+(1<<k-1)][j][k-1][l]); else { int a=max(dp[i][j][k-1][l-1],dp[i][j+(1<<l-1)][k-1][l-1]); int b=max(dp[i+(1<<k-1)][j][k-1][l-1],dp[i+(1<<k-1)][j+(1<<l-1)][k-1][l-1]); dp[i][j][k][l]=max(a,b); } } } int getmax(int x1,int y1,int x2,int y2) { int k=log2[x2-x1+1]; int l=log2[y2-y1+1]; int a=max(dp[x1][y1][k][l],dp[x2-(1<<k)+1][y1][k][l]); int b=max(dp[x1][y2-(1<<l)+1][k][l],dp[x2-(1<<k)+1][y2-(1<<l)+1][k][l]); return max(a,b); } int main() { int i,j,x1,y1,x2,y2; log2[1]=0; for(i=2;i<N;i++) log2[i]=log2[i-1]+!((i-1)&i); while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) for(j=1;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 0; }
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 1000000007 # define LL long long # define pb push_back # define F first # define S second # define N 505 # define M 10 int Max[N][N][M],Log2[N]; int a[N][N]; void initLog() //初始化Log2数组 { int i; Log2[0]=-1; for(i=1;i<N;i++) Log2[i]=Log2[i-1]+!(i&i-1); } void initRMQ(int n) { int i,j,k,lu,ld,ru,rd; for(k=0;(1<<k)<=n;k++) for(i=1;i+(1<<k)-1<=n;i++) for(j=1;j+(1<<k)-1<=n;j++) { if(k==0) Max[i][j][k]=a[i][j]; else { lu=Max[i][j][k-1]; //左上角 ld=Max[i+(1<<k-1)][j][k-1]; //左下角 ru=Max[i][j+(1<<k-1)][k-1]; //右上角 rd=Max[i+(1<<k-1)][j+(1<<k-1)][k-1]; //右下角 Max[i][j][k]=max(max(lu,ld),max(ru,rd)); } } } int Query(int x,int y,int l) { if(l==1) return a[x][y]; //注意 int k=Log2[l]; int lu=Max[x][y][k]; int ld=Max[x+l-(1<<k)][y][k]; int ru=Max[x][y+l-(1<<k)][k]; int rd=Max[x+l-(1<<k)][y+l-(1<<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=1;cas<=T;cas++) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;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 0; }
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 晴天小猪的神题