RMQ入门——[kuangbin]RMQ练习

RMQ区间最值查询，这类问题一般有多种方式可以解决，我使用的是ST稀疏表的形式，利用倍增的思想进行预处理然后实现O(1)的效率查询。

A - Balanced Lineup POJ - 3264

就是查询区间内的最大值和最小值的差，建两个st表就行了，这里我使用的递归方式建立的st表。

#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<vector> #include<string> #include<cmath> #include<set> #include<map> #include<queue> using namespace std; #define ll long long #define inf 0x3f3f3f3f const int mod = 1000000007; const int maxm = 105; const int maxn = 50005; const int M = 25; struct node{ int l, r, minn,maxx; }treenode[maxn*3]; int A[maxn]; int temp; int maxxx,minnn; void build(int i, int l, int r){ treenode[i].minn = inf; treenode[i].maxx = -inf; treenode[i].l = l; treenode[i].r = r; if (l == r){ treenode[i].maxx=treenode[i].minn = A[l]; return; } int m = (l + r) >> 1; build(i << 1, l, m); build(i << 1 | 1, m+1, r); treenode[i].maxx = max(treenode[i << 1].maxx, treenode[i<<1|1].maxx); treenode[i].minn = min(treenode[i << 1].minn, treenode[i<<1|1].minn); } void query(int i, int l, int r){ int lll = treenode[i].l, rrr = treenode[i].r; if (r<lll || l>rrr){ return; } if (l <= lll&&r >= rrr){ maxxx = max(maxxx, treenode[i].maxx); minnn = min(minnn, treenode[i].minn); return; } int m = (lll + rrr) >> 1; if(l<=m)query(i << 1, l, r); if(r> m)query(i << 1 | 1, l, r); } int n, q; int main() { int x, y; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++){ scanf("%d", &A[i]); } build(1, 1, n); for (int i = 0; i < q; i++){ scanf("%d%d", &x, &y); maxxx = -inf, minnn = inf; query(1, x, y); printf("%d\n",maxxx-minnn ); } return 0; }

B - Frequent values POJ - 3368

单调不下降（数据连续）求区间内出现最频繁的方式，ST表在处理区间最大最小值很有优势，这题中，如果众数出现的位置在ST表两段连续区间的分割处的话，使得该众数在这两段中都不是最多出现的，导致倍增表错误，因此在构造ST表时需要从中间向两端统计中间的数值出现的次数，与两个子表的值比较，查询时也需要这样做。

//计算lll的正确方式 lll=log(double(lll))/log(2.0) #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=100005; const int maxm=3000005; const int inf=0x3f3f3f3f; int n,q; int st[maxn][20]; int num[maxn]; void init(){ for(int i=0;i<n;i++)st[i][0]=1; for(int j=1;(1<<j)<=n;j++){ for(int i=0;i+(1<<j)-1<n;i++){ int rig=i+(1<<j)-1; st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); int cc=num[i+(1<<(j-1))]; int x=i+(1<<(j-1)),y=x; while(x-1>=i&&num[x-1]==cc)x--; while(y+1<=rig&&num[y+1]==cc)y++; st[i][j]=max(st[i][j],y-x+1); } } } int rmq(int lef,int rig){ int lll=rig-lef+1; lll=log(double(lll))/log(2.0); int ans=max(st[lef][lll],st[rig-(1<<lll)+1][lll]); int cc=num[rig-(1<<lll)+1]; int x=rig-(1<<lll)+1,y=x; while(x-1>=lef&&num[x-1]==cc)x--; while(y+1<=rig&&num[y+1]==cc)y++; int res=y-x+1; ans=max(res,ans); return ans; } int main() { while(scanf("%d",&n),n){ scanf("%d",&q); for(int i=0;i<n;i++){ scanf("%d",&num[i]); } init(); int a,b; for(int i=0;i<q;i++){ scanf("%d%d",&a,&b); printf("%d\n",rmq(a-1,b-1)); } } return 0; }

C - 降雨量 HYSBZ - 1067

中文题，处理回答比较麻烦

#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<vector> #include<string> #include<cmath> #include<set> #include<map> #include<queue> using namespace std; #define ll long long #define inf 0x3f3f3f3f //const int mod = 1000000007; const int maxm = 1000010; const int maxn = 50005; int n, c; int d[maxn][30]; int a[maxn]; int year[maxn]; void rmq_init(){ for (int i = 0; i <n; i++){ d[i][0] = a[i]; } for (int j = 1; (1 << j) <= n; j++){ for (int i = 0; i + (1 << j) - 1 <n; i++){ d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]); } } } int rmq(int l, int r){ if (l > r)return 0; int k = 0; while ((1 << (k + 1)) <= r - l + 1)k++; return max(d[l][k], d[r - (1 << k) + 1][k]); } int main() { int x, y; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d%d", &year[i], &a[i]); } rmq_init(); scanf("%d", &c); for (int i = 0; i < c; i++){ scanf("%d%d", &x, &y); if (x>y){ printf("false\n"); continue; } if (x == y){ printf("true\n"); continue; } int lef = lower_bound(year, year + n, x) - year; int l = year[lef]; int rig = lower_bound(year, year + n, y) - year; int r = year[rig]; if (l != x&&y != r){ printf("maybe\n"); } else if (l==x&&r != y){ int cc = rmq(lef + 1, rig - 1); if (cc < a[lef]){ printf("maybe\n"); } else{ printf("false\n"); } } else if(l!=x&&r==y){ int cc = rmq(lef, rig - 1); if (a[rig]>cc){ printf("maybe\n"); } else{ printf("false\n"); } } else{ if (a[rig] > a[lef]){ printf("false\n"); } else{ int cc = rmq(lef + 1, rig - 1); if (cc < a[rig]){ if (rig - lef == r - l){ printf("true\n"); } else{ printf("maybe\n"); } } else{ printf("false\n"); } } } } return 0; }

To the Max POJ - 1050

找最大子矩阵，我是用的DP完成的，前缀和处理1到i行每列之和，然后枚举起始行和终止行，转化成一维DP就最大值，复杂度为O(n^3)

//不知道跟rmq有什么关系 #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=100005; const int maxm=1005; const int inf=0x3f3f3f3f; int n,m; int matrix[105][105]; int qian[105][105]; int b[105]; int dp[105]; int main() { while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&matrix[i][j]); } } for(int j=0;j<n;j++){qian[0][j]=matrix[0][j];} for(int i=1;i<n;i++){ for(int j=0;j<n;j++){ qian[i][j]=qian[i-1][j]+matrix[i][j]; } } int ans=-inf; memset(b,0,sizeof(b)); for(int i=0;i<n;i++){ for(int k=i;k<n;k++){ for(int j=0;j<n;j++){ if(i) b[j]=qian[k][j]-qian[i-1][j]; else b[j]=qian[k][j]; } memset(dp,-inf,sizeof(dp)); dp[0]=b[0]; ans=max(ans,dp[0]); for(int j=1;j<n;j++){ dp[j]=max(b[j],b[j]+dp[j-1]); ans=max(ans,dp[j]); } } } printf("%d\n",ans); } }

E - Cornfields POJ - 2019

二维矩阵处理区间最大值和最小值之差，也是打两张表就行，因为矩阵和查询区间都是方阵，所以ST表只需要3个维度即可。

//因为矩阵为方形，st表只需要3个维度就行了 #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=255; const int maxm=1005; const int inf=0x3f3f3f3f; int n,b,k; int num[maxn][maxn]; int stmax[maxn][maxn][10]; int stmin[maxn][maxn][10]; void rmq_init(){ for(int i=0;i<n;i++){ for (int j=0;j<n;j++)stmax[i][j][0]=stmin[i][j][0]=num[i][j]; } for(int kk=1;(1<<kk)<=n;kk++){ for(int i=0;i+(1<<kk)-1<n;i++){ for(int j=0;j+(1<<kk)-1<n;j++){ stmax[i][j][kk]=max(max(stmax[i][j][kk-1],stmax[i+(1<<(kk-1))][j][kk-1]),max(stmax[i][j+(1<<(kk-1))][kk-1],stmax[i+(1<<(kk-1))][j+(1<<(kk-1))][kk-1])); stmin[i][j][kk]=min(min(stmin[i][j][kk-1],stmin[i+(1<<(kk-1))][j][kk-1]),min(stmin[i][j+(1<<(kk-1))][kk-1],stmin[i+(1<<(kk-1))][j+(1<<(kk-1))][kk-1])); } } } } int query(int x,int y,int xx,int yy){ int lll=log(double(b))/log(2.0); int maxx=max(max(stmax[x][y][lll],stmax[xx-(1<<(lll))+1][y][lll]),max(stmax[x][yy-(1<<lll)+1][lll],stmax[xx-(1<<lll)+1][yy-(1<<lll)+1][lll])); int minn=min(min(stmin[x][y][lll],stmin[xx-(1<<(lll))+1][y][lll]),min(stmin[x][yy-(1<<lll)+1][lll],stmin[xx-(1<<lll)+1][yy-(1<<lll)+1][lll])); return maxx-minn; } int main() { int x,y; scanf("%d%d%d",&n,&b,&k); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&num[i][j]); } } rmq_init(); for(int i=0;i<k;i++){ scanf("%d%d",&x,&y); x--;y--; printf("%d\n",query(x,y,x+b-1,y+b-1)); } }

F - Interviewe HDU - 3486

面试，把n个人分成m段，每一段选择值最大的那个人，问最少m为多少能满足所有选中的人的值加起来大于要求的指标。 满足二分的条件，所以只需要二分m，然后求每一段的最大值加起来看满足与否就行了。

//1 A,二分可行 #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=200005; const int maxm=1005; const int inf=0x3f3f3f3f; int n,k; int num[maxn]; int st[maxn][20]; void rmq_init(){ for(int i=0;i<n;i++){ st[i][0]=num[i]; } for(int j=1;(1<<j)<=n;j++){ for(int i=0;i+(1<<j)-1<n;i++){ st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int query(int x,int l){ int lll=log(double(l))/log(2); return max(st[x][lll],st[x+l-(1<<lll)][lll]); } bool solve(int m){ int len=n/m; int ans=0; for(int i=0;i<m;i++){ ans+=query(i*len,len); } if(ans>k)return 1; return 0; } int main() { while(~scanf("%d%d",&n,&k),n+k!=-2){ for(int i=0;i<n;i++){ scanf("%d",&num[i]); } rmq_init(); int lef=1,rig=n; int ans=-1; while(lef<=rig){ int mid=(lef+rig)/2; if(solve(mid)){ans=mid;rig=mid-1;} else lef=mid+1; } printf("%d\n",ans); } }

G - Find the hotel HDU - 3193

每一个旅馆有一个价格p和距离q，要求找出所有没有其他旅馆的价格和距离都比他小的旅馆，可以对其中一个值p或q排序，然后对于任意旅馆，查找1~（pi-1）的区间内又没有值小于qi，如果没有则输出。 不过其实不需要打ST表，遍历时用两个变量来维护最小值即可。

//我觉得这个方法更好，省空间，时间差不多 #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=10005; const int maxm=1005; const int inf=0x3f3f3f3f; int n,k; pair<int,int> p[maxn]; vector<pair<int,int> > ans; int main() { while(~scanf("%d",&n)){ ans.clear(); for(int i=0;i<n;i++){ scanf("%d%d",&p[i].first,&p[i].second); } sort(p,p+n); int totalmin=inf,cntmin=inf; int cnt=p[0].first; for(int i=0;i<n;i++){ if(p[i].first!=cnt){ cnt=p[i].first; totalmin=min(totalmin,cntmin); } cntmin=min(cntmin,p[i].second); if(totalmin>=p[i].second){ ans.push_back(p[i]); } } sort(ans.begin(),ans.end()); int ss=ans.size(); printf("%d\n",ss); for(int i=0;i<ss;i++){ printf("%d %d\n",ans[i].first,ans[i].second); } } }

H - Check Corners HDU - 2888

二维矩阵区间最大值查询以及最大值是否出现在矩阵四角。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100005; const int maxm=10000005; const int mod=998244353; int n,m,q; int st[301][301][9][9]; void rmq_init(){ for(int a=0;(1<<a)<=n;a++){ for(int b=0;(1<<b)<=m;b++){ if(a+b==0)continue; for(int i=0;i+(1<<a)-1<n;i++){ for(int j=0;j+(1<<b)-1<m;j++){ if(b) st[i][j][a][b]=max(st[i][j][a][b-1],st[i][j+(1<<(b-1))][a][b-1]); else st[i][j][a][b]=max(st[i][j][a-1][b],st[i+(1<<(a-1))][j][a-1][b]); } } } } } int query(int x1,int y1,int x2,int y2){ int a=log(double(x2-x1+1))/log(2.0); int b=log(double(y2-y1+1))/log(2.0); return max(max(st[x1][y1][a][b],st[x1][y2-(1<<b)+1][a][b]),max(st[x2-(1<<a)+1][y1][a][b],st[x2-(1<<a)+1][y2-(1<<b)+1][a][b])); } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&st[i][j][0][0]); } } rmq_init(); scanf("%d",&q); int a,b,c,d; while(q--){ scanf("%d%d%d%d",&a,&b,&c,&d); a--,b--,c--,d--; int ans=query(a,b,c,d); bool f=0; if(st[a][b][0][0]==ans||st[c][d][0][0]==ans||st[a][d][0][0]==ans||st[c][b][0][0]==ans)f=1; printf("%d ",ans); if(f)printf("yes\n"); else printf("no\n"); } } return 0; }

I - A Magic Lamp HDU - 3183

给你一串数字，可以删除其中m个数字，问怎么删使得删完后结果最小。 要使得高位尽量小，已知删完后的位数，就知道删完后的最高位可以是原序列的哪段区间，选取区间最小的那个，然后一次类推。

// i don't know why my solution is wa #include<string.h> #include<cstdio> #include<queue> #include<map> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define MEM(a,b) memset(a,b,sizeof(a)); typedef long long ll; const int maxn=1005; const int maxm=1005; const int inf=0x3f3f3f3f; int n,m; char s[maxn]; int num[maxn]; int place[maxn][12]; int st[maxn][12]; void rmq_init(){ for(int i=0;i<n;i++){st[i][0]=num[i];place[i][0]=i;} for(int j=1;(1<<j)<=n;j++){ for(int i=0;i+(1<<j)-1<n;i++){ if(st[i][j-1]<=st[i+(1<<(j-1))][j-1]){ st[i][j]=st[i][j-1]; place[i][j]=place[i][j-1]; } else{ st[i][j]=st[i+(1<<(j-1))][j-1]; place[i][j]=place[i+(1<<(j-1))][j-1]; } } } } int query(int x,int len){ len=len-x+1; int lll=log(double(len))/log(2.0); if(st[x][lll]<=st[x+len-(1<<lll)][lll])return place[x][lll]; else return place[x+len-(1<<lll)][lll]; } int main() { while(~scanf("%s%d",s,&m)){ n=strlen(s); for(int i=0;i<n;i++)num[i]=s[i]-'0'; rmq_init(); if(m>=n){printf("0\n");continue;} int cnt=0; int kk=m; bool f=0; bool ssss=0; for(int i=0;i<n-m;i++){ int pp=query(cnt,kk+i); cnt=pp+1; if(s[pp]!='0')f=1; if(f==0&&s[pp]=='0')continue; putchar(s[pp]); ssss=1; } if(ssss==0)printf("0"); printf("\n"); } }

J - Phalanx HDU - 2859

找最大对称子矩阵，也是用的DP来做，不懂得如何用RMQ做。

#include<iostream> #include<stdio.h> using namespace std; int n; char m[1005][1005]; int dp[1005][1005]; int main() { while (~scanf("%d", &n), n){ int ans = 1; for (int i = 0; i < n; i++){ scanf("%s", m[i]); for (int j = 0; j < n; j++){ dp[i][j] = 1; } } for (int i = 1; i < n; i++){ for (int j = 0; j < n-1; j++){ int k = 1; while (j + k < n&&i - k >= 0 && m[i][j + k] == m[i - k][j]){ k++; } if (k >= dp[i - 1][j + 1] + 1)dp[i][j] = dp[i - 1][j + 1] + 1; else{ dp[i][j] = k; } ans = max(ans, dp[i][j]); } } printf("%d\n", ans); } return 0; }