POJ-2019: Cornfields（2维RMQ）

RMQ

链接：POJ-2019

Description

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，b，q；表示一个n*n的数字矩形，q次询问以（a，b）为左上角的边长为b的正方形内数字最大值与最小值的差为多少。

分析：数据很水，可以暴力过……正解应该是二维线段树或者RMQ，不会二维线段树，二维RMQ也不会……
最开始把n*n的矩形摊开放到数组里，用普通的线段树进行b次查询每个宽度为b的区间里的最大最小值，然后超时了……比暴力还慢ORZ
这是从网上找了一个模板…

• 代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int mp[255][255];
int dpmin[255][255][8][8]; //若起点为(0,0),2^8=256
int dpmax[255][255][8][8];
//二维RMQ，dp[x][y][i][j] 
//表示从(x,y)点到右下角为(x+2^i-1,y+2^j-1)矩形内最小值
void RMQ(int n,int m) //n*m的矩阵
{
    for(int i=0;(1<<i)<=n;i++)
    {
        for(int j=0;(1<<j)<=m;j++)
        {
            if(!i&&!j)  continue;
            for(int r=1;r+(1<<i)-1<=n;r++)
                for(int c=1;c+(1<<j)-1<=m;c++)
            {
                if(!j)
                {
                    dpmax[r][c][i][j]=max(dpmax[r][c][i-1][j],dpmax[r+(1<<(i-1))][c][i-1][j]);
                    dpmin[r][c][i][j]=min(dpmin[r][c][i-1][j],dpmin[r+(1<<(i-1))][c][i-1][j]);
                }
                else
                {
                    dpmax[r][c][i][j]=max(dpmax[r][c][i][j-1],dpmax[r][c+(1<<(j-1))][i][j-1]);
                    dpmin[r][c][i][j]=min(dpmin[r][c][i][j-1],dpmin[r][c+(1<<(j-1))][i][j-1]);
                }
            }
        }
    }
}
int querymax(int lx,int ly,int rx,int ry)
{
    int kx=0,ky=0;
    while(lx+(1<<(1+kx))-1<=rx) kx++;
    while(ly+(1<<(1+ky))-1<=ry) ky++;
    int m1=dpmax[lx][ly][kx][ky];
    int m2=dpmax[rx-(1<<kx)+1][ly][kx][ky];
    int m3=dpmax[lx][ry-(1<<ky)+1][kx][ky];
    int m4=dpmax[rx-(1<<kx)+1][ry-(1<<ky)+1][kx][ky];
    return max(max(m1,m2),max(m3,m4));
}
int querymin(int lx,int ly,int rx,int ry)
{
    int kx=0,ky=0;
    while(lx+(1<<(1+kx))-1<=rx) kx++;
    while(ly+(1<<(1+ky))-1<=ry) ky++;
    int m1=dpmin[lx][ly][kx][ky];
    int m2=dpmin[rx-(1<<kx)+1][ly][kx][ky];
    int m3=dpmin[lx][ry-(1<<ky)+1][kx][ky];
    int m4=dpmin[rx-(1<<kx)+1][ry-(1<<ky)+1][kx][ky];
    return min(min(m1,m2),min(m3,m4));
}
int main()
{
    int n,b,q;
    scanf("%d%d%d",&n,&b,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        scanf("%d",&mp[i][j]);
        dpmax[i][j][0][0]=mp[i][j];
        dpmin[i][j][0][0]=mp[i][j];
    }
    RMQ(n,n);
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",querymax(x,y,x+b-1,y+b-1)-querymin(x,y,x+b-1,y+b-1));
    }
    return 0;
}