Cornfields
题目链接：
http://poj.org/problem?id=2019
题意：
求矩形区间最大值和最小值的差
题解：
二维RMQ，但是题目时间限制比较宽松，直接再一维RMQ上加一重for循环也行
代码
#include<stdio.h>
#include<math.h>
const int N=251;
int dpmax[N][N][10];
int dpmin[N][N][10];
int mmax(int x,int y)
{
return x>y?x:y;
}
int mmin(int x,int y)
{
return x<y?x:y;
}
void Make_Rmq(int n)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&dpmax[i][j][0]);
dpmin[i][j][0]=dpmax[i][j][0];
}
for(int k=1;(1<<k)<=n;++k)
{
for(int i=1;i<=n;++i)
for(int j=1;j+(1<<k)-1<=n;++j)
{
dpmax[i][j][k]=mmax(dpmax[i][j][k-1],dpmax[i][j+(1<<k-1)][k-1]);
dpmin[i][j][k]=mmin(dpmin[i][j][k-1],dpmin[i][j+(1<<k-1)][k-1]);
}
}
}
int Get_Rmq(int x,int y,int B)
{
int k=(int)(log(B*1.0)/log(2.0));
int ma=0,mi=100000;
for(int i=x;i<=x+B-1;++i)
{
if(mmax(dpmax[i][y][k],dpmax[i][y+B-(1<<k)][k])>ma)ma=mmax(dpmax[i][y][k],dpmax[i][y+B-(1<<k)][k]);
if(mmin(dpmin[i][y][k],dpmin[i][y+B-(1<<k)][k])<mi)mi=mmin(dpmin[i][y][k],dpmin[i][y+B-(1<<k)][k]);
}
return ma-mi;
}
void solve()
{
int B,Q,n,l,r;
while(~scanf("%d%d%d",&n,&B,&Q))
{
Make_Rmq(n);
while(Q--)
{
scanf("%d%d",&l,&r);
printf("%d
",Get_Rmq(l,r,B));
}
}
}
int main()
{
solve();
return 0;
}