①一维RMQ
(1) dp[i,j] 表示从第i个数起连续2j个数中的（最大值min、最小值max、最大公约数gcd……），通过更改下列代码中的红色函数即可实现。
(2) b数组放置所需查询的数列。
const int MAX=305; int dp[MAX][20]; int mm[MAX]; void initrmq(int n,int b[]) { mm[0]=-1; for(int i=1;i<=n;i++) { mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; dp[i][0]=b[i]; } for(int j=1;j<=mm[n];j++) for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } ll rmq(int x,int y) { int k=mm[y-x+1]; return max(dp[x][k],dp[y-(1<<k)+1][k]); }
②二维RMQ
给定一个n*m矩阵，每次询问左上角(r1,c1)到右下角(r2,c2)的子矩形中的（最大值min、最小值max、最大公约数gcd……）并输出。如果每次所询问的四个角有符合条件的数，输出yes，否则输出no。
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> #include<map> using namespace std; typedef long long ll; const int MAX=305; int val[MAX][MAX]; int dp[MAX][MAX][9][9];//最大值 int mm[MAX]; void initRMQ(int n,int m)//m*n的矩阵 { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j][0][0]=val[i][j]; for(int ii=0;ii<=mm[n];ii++) for(int jj=0;jj<=mm[m];jj++) if(ii+jj) for(int i=1;i+(1<<ii)-1<=n;i++) for(int j=1;j+(1<<jj)-1<=m;j++) if(ii)dp[i][j][ii][jj]=max(dp[i][j][ii-1][jj],dp[i+(1<<(ii-1))][j][ii-1][jj]); else dp[i][j][ii][jj]=max(dp[i][j][ii][jj-1],dp[i][j+(1<<(jj-1))][ii][jj-1]); } int rmq(int x1,int y1,int x2,int y2)//所查询矩形区间内的最大值 左上角(x1,y1) -> 右上角(x2,y2) { int k1=mm[x2-x1+1]; int k2=mm[y2-y1+1]; x2=x2-(1<<k1)+1; y2=y2-(1<<k2)+1; return max(max(dp[x1][y1][k1][k2],dp[x1][y2][k1][k2]),max(dp[x2][y1][k1][k2],dp[x2][y2][k1][k2])); } int main() { mm[0]=-1; for(int i=1;i<=MAX;i++) mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; int n,m,Q; int r1,c1,r2,c2; while(scanf("%d%d",&n,&m)==2) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&val[i][j]); initRMQ(n,m); scanf("%d",&Q); while(Q--) { scanf("%d%d%d%d",&r1,&c1,&r2,&c2);//左上角(r1,c1) -> 右上角(r2,c2) if(r1>r2)swap(r1,r2); if(c1>c2)swap(c1,c2); int tmp=rmq(r1,c1,r2,c2); printf("%d ",tmp); if(tmp==val[r1][c1]||tmp==val[r1][c2]||tmp==val[r2][c1]||tmp==val[r2][c2]) printf("yes "); else printf("no "); } } return 0; }
③二维RMQ降维
给定一个n*n(n<=500)的矩阵（即是正方形)，每次询问以(x,y)为左上角，边长为s的正方形区域内的最大值。
dp[i][j][k]：以(i,j)为左上角，边长为2^k的正方形区域内的最大值。
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const int MAX=505; int dp[MAX][MAX][10],mm[MAX],val[MAX][MAX]; void initrmq(int n) { int lt,lb,rt,rb; for(int k=0;k<=mm[n];k++) for(int i=1;i+(1<<k)-1<=n;i++) for(int j=1;j+(1<<k)-1<=n;j++) if(k==0) dp[i][j][k]=val[i][j]; else { lt=dp[i][j][k-1]; //左上角 lb=dp[i+(1<<k-1)][j][k-1]; //左下角 rt=dp[i][j+(1<<k-1)][k-1]; //右上角 rb=dp[i+(1<<k-1)][j+(1<<k-1)][k-1];//右下角 dp[i][j][k]=max(max(lt,lb),max(rt,rb)); } } int rmq(int x,int y,int s) { if(s==1)return val[x][y]; int k=mm[s]; int lt=dp[x][y][k]; int lb=dp[x+s-(1<<k)][y][k]; int rt=dp[x][y+s-(1<<k)][k]; int rb=dp[x+s-(1<<k)][y+s-(1<<k)][k]; return max(max(lt,lb),max(rt,rb)); } int main() { int i,j,k,T; mm[0]=-1; for(i=1;i<=MAX;i++) mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { int n,q; scanf("%d%d",&n,&q); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&val[i][j]); initrmq(n); printf("Case %d: ",cas); while(q--) { int x,y,s; scanf("%d%d%d",&x,&y,&s); printf("%d ",rmq(x,y,s)); } } return 0; }