二维RMQ
二维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;
//RMQ预处理；
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)//第i行的一维RMQ中，从第j个数开始，长度为1的范围中，最大值最小值都是他自己；相当于一维数组中的maxx[i][0] = minn[i][0] = x;
{
maxx[i][j][k] = minn[i][j][k] = mapp[i][j];
}
else //第i行的一维RMQ;
{
maxx[i][j][k] = max(maxx[i][j][k-1], maxx[i][j+(1<<(k-1))][k-1]);
minn[i][j][k] = min(minn[i][j][k-1], minn[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(maxx[x][y][k], maxx[x][y1-(1<<k)+1][k]);
for(int i=x+1;i<=x1;i++)
mm = max(mm,max(maxx[i][y][k],maxx[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(minn[x][y][k], minn[x][y1-(1<<k)+1][k]);
for(int i=x+1;i<=x1;i++)
mm = min(mm,min(minn[i][y][k], minn[i][y1-(1<<k)+1][k]));
return mm;
}第二种方法：
首先，dp[ i ][ j ][ k ][ l ]表示从第一个点也就是左下角（i，j）起，横坐标长度为2^k, 纵坐标长度为2^l，即右上角（i+2^k-1，j+2^k-1）中的最大值。
一维RMQ是把一个区间划分成两个区间求最值，同理，在二维RMQ中，我们可以把一个大的矩阵划分成四个小矩阵求最值
但是要考虑到一种特殊情况：这个矩阵行为1或列为1时，需要特判断。
一共四种情况：
一个点：k=0，l=0（从点(i, j)横纵坐标长度都为1，所包含的点的最大值，即只有它本身） maxx[ i ][ j ][ k ][ l ] = mapp[ i ][ j ];
一列： k=0，l!=0（从点(i, j)横坐标长度为1，送坐标长度>1所包含的点的最大值，即矩阵为一列）maxx[ i ][ j ][ k ][ l ] = max(maxx[ i ][ j ][ k ][ l-1 ],maxx[ i ][ j+(1<<(l-1)) ][ k ][ l-1 ]);
一行： k!=0，l=0（从点(i, j)横坐标长度>1，纵坐标长度为1所包含的点的最大值，即矩阵为一行）maxx[ i ][ j ][ k ][ l ] = max(maxx[ i ][ j ][ k-1 ][ l ],maxx[ i+(1<<(k-1)) ][ j ][ k-1 ][ l ]);
其他： maxx[ i ][ j ][ k ][ l ] = maxm(maxx[ i ][ j ][ k-1 ][ l-1 ],maxx[ i+(1<<(k-1)) ][ j ][ k-1 ][ l-1 ], maxx[ i ][ j+(1<<(l-1)) ][ k-1 ][ l-1 ], maxx[ i+(1<<(k-1)) ][ j+(1<<(l-1)) ][ k-1 ][ l-1 ]);
同一维一样， 用maxx[i][j][k][l]表示左下角（i, j）到右上角（i+2^k, j+2^l）矩形内的最值，初始化maxx的时候，maxx[i][j][0][0] = mapp[i][j]，接着用4层for去循环更新
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &mapp[i][j]);
maxx[i][j][0][0] = mapp[i][j];
}
}
for (int k=0; (1<<k)<=n; k++)
{
for (int l=0; (1<<l)<=m; l++)
{
if (k==0&&l==0)
continue;//矩阵只有一个点；
for (int i=1; i+(1<<k)-1<= n; i++)
{
for (int j=1; j+(1<<l)-1<=m; j++)
{
//当x或y等于0的时候，就相当于一维的RMQ了
if (k == 0) //矩阵为一列；
maxx[i][j][k][l] = max(maxx[i][j][k][l-1], maxx[i][j+(1<<(j-1))][i][j-1]);
else if (l == 0) //矩阵为一行；
maxx[i][j][k][l] = max(maxx[i][j][k-1][l], maxx[i+(1<<(k-1))][j][k-1][l]);
else //不是特殊矩阵；
maxx[i][j][k][l] = max(maxx[i][j][k][l-1], maxx[i][j+(1<<(j-1))][k][l-1]);
}
}
}
}
例题：
FJ has decided to grow his own corn hybrid in order to help the cows make the best possible milk. To that end, he's looking to build the cornfield on the flattest piece of land he can find.
FJ has, at great expense, surveyed his square farm of N x N hectares (1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation <= 250) associated with it.
FJ will present your program with the elevations and a set of K (1 <= K <= 100,000) queries of the form "in this B x B submatrix, what is the maximum and minimum elevation?". The integer B (1 <= B <= N) is the size of one edge of the square cornfield and is a constant for every inquiry. Help FJ find the best place to put his cornfield.
Input
* Line 1: Three space-separated integers: N, B, and K.
* Lines 2..N+1: Each line contains N space-separated integers. Line 2 represents row 1; line 3 represents row 2, etc. The first integer on each line represents column 1; the second integer represents column 2; etc.
* Lines N+2..N+K+1: Each line contains two space-separated integers representing a query. The first integer is the top row of the query; the second integer is the left column of the query. The integers are in the range 1..N-B+1.
Output
* Lines 1..K: A single integer per line representing the difference between the max and the min in each query.
Sample Input
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
Sample Output
5题意：给出一个N*N的矩阵，和边长B，以及K次询问，然后给出一个点（Xi，Yi），输出，在以给出的点为左上角的点，边长为B的子矩阵中，最大值与最小值的差；
#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 maxx[MAXN][MAXN][10][10];
int minn[MAXN][MAXN][10][10];
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)
{
minn[i][j][k][l]=maxx[i][j][k][l]=rec[i][j];
}
else if(k==0)
{
maxx[i][j][k][l]=max(maxx[i][j][k][l-1],maxx[i][j+(1<<(l-1))][k][l-1]);
minn[i][j][k][l]=min(minn[i][j][k][l-1],minn[i][j+(1<<(l-1))][k][l-1]);
//printf("%d %d\n",maxx[i][j][k][l-1],maxx[i][j+(1<<(l-1))][k][l-1]);
}
else if(l==0)
{
maxx[i][j][k][l]=max(maxx[i][j][k-1][l],maxx[i+(1<<(k-1))][j][k-1][l]);
minn[i][j][k][l]=min(minn[i][j][k-1][l],minn[i+(1<<(k-1))][j][k-1][l]);
//printf("%d %d\n",maxx[i][j][k-1][l],maxx[i+(1<<(k-1))][j][k-1][l]);
}
else
{
maxx[i][j][k][l]=maxm(maxx[i][j][k-1][l-1],maxx[i+(1<<(k-1))][j][k-1][l-1],maxx[i][j+(1<<(l-1))][k-1][l-1],maxx[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
minn[i][j][k][l]=minm(minn[i][j][k-1][l-1],minn[i+(1<<(k-1))][j][k-1][l-1],minn[i][j+(1<<(l-1))][k-1][l-1],minn[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
//printf("%d %d %d %d\n",maxx[i][j][k-1][l-1],maxx[i+(1<<(k-1))][j][k-1][l-1],
//maxx[i][j+(1<<(l-1))][k-1][l-1],maxx[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
}
//printf("i:%d j:%d k:%d l:%d maxx:%d\n",i,j,k,l,maxx[i][j][k][l]);
//system("pause");
}
}
}
}
}
int rmq2dmax(int x,int y,int x1,int y1)
{
//if(x==x1&&y==y1)return maxx[x][y][0][0];
int k=log(x1-x+1)/log(2);
int l=log(y1-y+1)/log(2);
return maxm(maxx[x][y][k][l],maxx[x1-(1<<k)+1][y][k][l],maxx[x][y1-(1<<l)+1][k][l],maxx[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(minn[x][y][k][l],minn[x1-(1<<k)+1][y][k][l],minn[x][y1-(1<<l)+1][k][l],minn[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);
}
/*
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stack>
#include <map>
#include <queue>
using namespace std;
#define ll __int64
#define lll unsigned long long
#define MAX 1000009
#define eps 1e-8
//二维RMQ模板题
//同一维一样 用maxx[row][col][i][j]表示从左上角(row,col)到右下角(row+2^i,col+2^j)所围成的矩形内的最大值；
int mapp[309][309];
int dp[309][309][9][9];
int flag;
//二维RMQ 初始化从左上角（1，1）到右下角（m，n）；
void RMQ2(int m,int n)
{
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
maxx[i][j][0][0] = mapp[i][j];
}
}
int k = log((double)n)/log(2.0);
for(int i=0; i<=k; i++)
{
for(int j=0; j<=k; j++)
{
if(i==0&&j==0)
continue;
for(int row=1; row+(1<<i)-1<=m; row++)
{
for(int col=1; col+(1<<j)-1<=n; col++)
{
if(i)
maxx[row][col][i][j] = max(maxx[row][col][i-1][j],maxx[row+(1<<(i-1))][col][i-1][j]);
else
maxx[row][col][i][j] = max(maxx[row][col][i][j-1],maxx[row][col+(1<<(j-1))][i][j-1]);
}
}
}
}
}
//查询从左上角（x1,y1）到右下角（x2, y2）的最大值；
int RMQ_2d(int x1,int y1,int x2,int y2)
{
int k1 = log(double(x2-x1+1))/log(2.0);
int k2 = log(double(y2-y1+1))/log(2.0);
int m1 = maxx[x1][y1][k1][k2];
int m2 = maxx[x2-(1<<k1)+1][y1][k1][k2];
int m3 = maxx[x1][y2-(1<<k2)+1][k1][k2];
int m4 = maxx[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2];
int maxxx = max(max(m1,m2),max(m3,m4));
if(mapp[x1][y1]==maxxx||mapp[x1][y2]==maxxx||mapp[x2][y1]==maxxx||mapp[x2][y2]==maxxx)
flag = 1;
return maxxx;
}
int main()
{
int n,m,t;
int x1,x2,y1,y2;
while(~scanf("%d%d",&m,&n))
{
for(int i = 1; i<=m; i++)
{
for(int j = 1; j<=n; j++)
{
scanf("%d",&mapp[i][j]);
}
}
RMQ2(m,n);
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
flag = 0;
int maxxx = RMQ_2d(x1,y1,x2,y2);
if(flag == 1)
printf("%d yes\n",maxxx);
else
printf("%d no\n",maxxx);
}
}
return 0;
}