POJ 2019 Cornfields （线段树）

模型：给定一个整数矩阵，查询某个子矩阵中的最大数与最小数之差。N最大为250，查询数K最大为100000

我的做法：用线段树求出要查询的子矩阵每一行的最大与最小，然后在列方向上统计子矩阵的最大与最小。有点暴力，跑了800+ms。

#include <stdio.h>
#include <string.h>
#define N 255
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
int n,b,k,D;
int max[N][4*N];
int min[N][4*N];
void update(int i,int cur)
{
    int ls=cur<<1,rs=cur<<1|1;
    max[i][cur]=MAX(max[i][ls],max[i][rs]);
    min[i][cur]=MIN(min[i][ls],min[i][rs]);
}
void init()
{
    int i,j;
    for(D=1;D<n+2;D<<=1);
    memset(max,0,sizeof(max));
    memset(min,0x3f,sizeof(min));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            int a;
            scanf("%d",&a);
            max[i][j+D]=min[i][j+D]=a;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=D-1;j;j--)    update(i,j);
    }
}
int query_max(int row,int x,int y)
{
    int i=x+D-1,j=y+D+1,ret=0;
    for(;i^j^1;i>>=1,j>>=1)
    {
        if(!(i&1))    ret=MAX(ret,max[row][i^1]);
        if(j&1) ret=MAX(ret,max[row][j^1]);
    }
    return ret;
}
int query_min(int row,int x,int y)
{
    int i=x+D-1,j=y+D+1,ret=250;
    for(;i^j^1;i>>=1,j>>=1)
    {
        if(!(i&1))    ret=MIN(ret,min[row][i^1]);
        if(j&1) ret=MIN(ret,min[row][j^1]);
    }
    return ret;
}
int query(int x,int y)
{
    int min_ans=250,max_ans=0;
    for(int row=x;row<x+b;row++)
    {
        min_ans=MIN(min_ans,query_min(row,y,y+b-1));
        max_ans=MAX(max_ans,query_max(row,y,y+b-1));
    }
    return max_ans-min_ans;
}
int main()
{
    while(~scanf("%d%d%d",&n,&b,&k))
    {
        init();
        while(k--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",query(x,y));
        }
    }
    return 0;
}