poj 2019 Cornfields【RMQ】

这道题是poj上一道还比较有名的二维RMQ (Range Minimum/Maximum Query 局部最大最小查询)问题，但是可能是这道题的数据设计的不是很好，所以可以直接暴力过，先上暴力AC版本的代码，之后会贴出RMQ正经版的代码。。。

RMQ问题（区间询问最值问题）。
题目大意：给出一个N*N矩形，每个格子上有一个价值。询问一个b*b的矩形在左上角的位置(x,y)，(x+b-1,y+b-1)这一部分的最大值-最小值是多少。
题目分析：询问次数很多，但是矩形只有250且是正方形。二维的RMQ！

另外说一点，在poj评测时如果函数不返回值会编译错误，一定要int返回型定义main函数。

#include<stdio.h>

#define MAXN 260
#define bigInt 100000

int bigLand[MAXN][MAXN]; //大块土地

void work(int x,int y,int B)
{
	//从坐标为(x,y)的地方开始
	int i,j;
	int max=-1;
	int min=bigInt;
	for (i=x;i<=x+B-1;i++)
	{
		for(j=y;j<=y+B-1;j++)
		{
			if (bigLand[i][j]>max)
				max=bigLand[i][j];

			if(bigLand[i][j]<min)
				min=bigLand[i][j];
		}
	}

	printf("%d\n",max-min);
}


int main()
{
	//暴力解法
	int N; //大块土地边长
	int B; //指定的小块土地边长
	int K; //查询次数

	int x,y; //每次查询的坐标
	int i,j;

	while(scanf("%d%d%d",&N,&B,&K)!=EOF)
	{
		for (i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				scanf("%d",&bigLand[i][j]);

		for(i=0;i<K;i++)
		{
			scanf("%d%d",&x,&y);
			work(x,y,B); //处理函数
		}
	}


	return 0;
}

下面是引用一位大牛的分析，讲的很不错

RMQ问题ST算法

1<<n是把1 按2进制 左移n位，开始 1 的2进制表示是 0000 0001

1<<2是4,1<<3是8，所以1<<n相当于2^n

1<<16是65536

使用RMQ的AC代码：

#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cmath>

#define MAXN 260

using namespace std;

int bigLand[MAXN][MAXN]; //大块土地
int pmax[MAXN][MAXN][11],pmin[MAXN][MAXN][11];

int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }

void init_rmq(int n)
{
	int i;
	for(i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            pmax[i][j][0]=pmin[i][j][0]=bigLand[i][j];
		
	for(i=1;i<=n;i++)
		for(int k=1;(1<<k)<=n;k++)
			for(int j=1;j+(1<<k)-1<=n;j++)
			{
				pmax[i][j][k]=max(pmax[i][j][k-1],pmax[i][j+(1<<(k-1))][k-1]);
				pmin[i][j][k]=min(pmin[i][j][k-1],pmin[i][j+(1<<(k-1))][k-1]);
			}
}



void work(int x,int y,int B)
{
	//从坐标为(x,y)的地方开始
	int k=(int)(log(double(B))/log(2.0));
    int maxans=-1; int minans=0x3f3f3f3f;
    int l=y,r=y+B-1;
    for(int i=x;i<x+B;i++)
    {
        maxans=max(maxans,max(pmax[i][l][k],pmax[i][r-(1<<k)+1][k]));
        minans=min(minans,min(pmin[i][l][k],pmin[i][r-(1<<k)+1][k]));
    }
	
	printf("%d\n",maxans-minans);
}


int main()
{
	//RMQ解法
	int N; //大块土地边长
	int B; //指定的小块土地边长
	int K; //查询次数
	
	int x,y; //每次查询的坐标
	int i,j;
	
	while(scanf("%d%d%d",&N,&B,&K)!=EOF)
	{
		for (i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				scanf("%d",&bigLand[i][j]);
			
		init_rmq(N);

		for(i=0;i<K;i++)
		{
			scanf("%d%d",&x,&y);
			work(x,y,B); //处理函数
		}
	}
	
	
	return 0;
}