RMQ可以用来查找区间最值（最大或最小）
二维RMQ可以用来求子矩阵的最值问题。
RMQ先将所有起点的向后跳2^i的数最值求出来，然后查询的时候再查找两个区间
dp[i][j]表示i~i+2^j-1这2^j个数中的最值，如果用区间表示的话，就是
[i,i+2^j)
这样的话我们可以得到一个公式
dp[i][j]=max(dp[i][j-1],dp[i+(1<<j)][j-1];
i~2^j-1可以分成求两个区间的最值[i,i+2^j)--> max [i,i+2^(j-1)) [i+2^(j-1),i+2^j)
区间的最值是可以合并的。
一维数组使用RMQ的话时间复杂度是
O(n*log(n))-O(1)
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN 200010
const int N_N=log2(MAXN)+2;
int n,k;
int d[MAXN][N_N];
int a[MAXN];
inline int max(int a, int b) {
return a > b ? a : b;
}
void st() {
int m, i, j;
for(int i=1;i<=n;i++)
d[i][0]=a[i];
//m = (int) (log((double) n) / log(2.0));
m=log2(n);
for (j = 1; j <= m; ++j) {
for (i = 1; i + (1 << j) - 1 <= n; ++i)
d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
int rmq(int a, int b) {
int m = (int) (log(b - a + 1.0) / log(2.0));
return max(d[a][m], d[b - (1 << m) + 1][m]);
}
int main()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int t;
st();
scanf("%d",&t);
while(t--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",rmq(a,b));
}
}
return 0;
}
二维RMQ
两种做法：
1) O(n*m*log(m))-O(n)
2) O(n*m*log(n)*log(m)-O(1)
第一种很好理解。
把每一行都当成一维RMQ处理
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 250
int dp[MAXN][MAXN][20];
int dp1[MAXN][MAXN][20];
int a[MAXN][MAXN];
int n,m;
void st(){
for(int i=1;i<=n;i++)
for(int k=0;(1<<k)<=m;k++){
for(int j=1;j+(1<<k)-1<=m;j++){
if(k==0){
dp[i][j][k]=dp1[i][j][k]=a[i][j];
}
else {
dp[i][j][k]=max(dp[i][j][k-1],dp[i][j+(1<<(k-1))][k-1]);
dp1[i][j][k]=min(dp1[i][j][k-1],dp1[i][j+(1<<(k-1))][k-1]);
}
}
}
}
int rmq2dmax(int x,int y,int x1,int y1){
int k=log2(y1-y+1);
int mm=max(dp[x][y][k],dp[x][y1-(1<<k)+1][k]);
for(int i=x+1;i<=x1;i++)
mm=max(mm,max(dp[i][y][k],dp[i][y1-(1<<k)+1][k]));
return mm;
}
int rmq2dmin(int x,int y,int x1,int y1){
int k=log2(y1-y+1);
int mm=min(dp1[x][y][k],dp1[x][y1-(1<<k)+1][k]);
for(int i=x+1;i<=x1;i++)
mm=min(mm,min(dp1[i][y][k],dp1[i][y1-(1<<k)+1][k]));
return mm;
}
第二种方法。
可以把一个大矩阵划分成四个小矩阵求最值
但是要考虑到这个矩阵行为1或列为1的情况。需要特判断。
dp[i][j][k][l]-->代表i~i+2^k j~j+2^l 这个矩阵中的最大值
三种情况
k=0 l=0 dp[i][j][k][l]=a[i][j];
k=0 l!=0 dp[i][j][k][l]=max(dp[i][j][k][l-1],dp[i][j+(1<<(l-1))][k][l-1]);
k!=0 l=0 dp[i][j][k][l]=max(dp[i][j][k-1][l],dp[i+(1<<(k-1))][j][k-1][l]);
其他 dp[i][j][k][l]=maxm(dp[i][j][k-1][l-1],dp[i+(1<<(k-1))][j][k-1][l-1],
dp[i][j+(1<<(l-1))][k-1][l-1],dp[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
可以拿笔在纸上画画。很容易推出这个方程。
这里有一道题戳我= =用这种方法居然MLE 我去。使用了O(n*m*log(m)-O(n)的复杂度才过。
好了，代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 300
int rec[MAXN][MAXN];
int dp[MAXN][MAXN][10][10];
int dp1[MAXN][MAXN][10][10];
//dp-->max
//dp1-->min
int n,m;
inline int maxm(int a,int b,int c,int d){
if(a<b)a=b; if(a<c)a=c; if(a<d)a=d;
return a;
}
inline int minm(int a,int b,int c,int d){
if(b<a)a=b; if(c<a)a=c; if(d<a)a=d;
return a;
}
void st()
{
for(int k=0;(1<<k)<=n;k++)
for(int l=0;(1<<l)<=m;l++)
for(int i=1;i+(1<<k)-1<=n;i++)
for(int j=1;j+(1<<l)-1<=m;j++)
{
if(!k&&!l){
dp1[i][j][k][l]=dp[i][j][k][l]=rec[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]);
dp1[i][j][k][l]=min(dp1[i][j][k][l-1],dp1[i][j+(1<<(l-1))][k][l-1]);
//printf("%d %d\n",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]);
dp1[i][j][k][l]=min(dp1[i][j][k-1][l],dp1[i+(1<<(k-1))][j][k-1][l]);
//printf("%d %d\n",dp[i][j][k-1][l],dp[i+(1<<(k-1))][j][k-1][l]);
}
else {
dp[i][j][k][l]=maxm(dp[i][j][k-1][l-1],dp[i+(1<<(k-1))][j][k-1][l-1],
dp[i][j+(1<<(l-1))][k-1][l-1],dp[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
dp1[i][j][k][l]=minm(dp1[i][j][k-1][l-1],dp1[i+(1<<(k-1))][j][k-1][l-1],
dp1[i][j+(1<<(l-1))][k-1][l-1],dp1[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
//printf("%d %d %d %d\n",dp[i][j][k-1][l-1],dp[i+(1<<(k-1))][j][k-1][l-1],
//dp[i][j+(1<<(l-1))][k-1][l-1],dp[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
}
//printf("i:%d j:%d k:%d l:%d dp:%d\n",i,j,k,l,dp[i][j][k][l]);
//system("pause");
}
}
int rmq2dmax(int x,int y,int x1,int y1){
//if(x==x1&&y==y1)return dp[x][y][0][0];
int k=log(x1-x+1)/log(2);
int l=log(y1-y+1)/log(2);
return maxm(dp[x][y][k][l],dp[x1-(1<<k)+1][y][k][l],
dp[x][y1-(1<<l)+1][k][l],dp[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);
}
int rmq2dmin(int x,int y,int x1,int y1){
int k=log(x1-x+1)/log(2);
int l=log(y1-y+1)/log(2);
return minm(dp1[x][y][k][l],dp1[x1-(1<<k)+1][y][k][l],
dp1[x][y1-(1<<l)+1][k][l],dp1[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);
}