| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 5516 | Accepted: 2714 |
Description
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
* 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
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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define N 255 int n,b,k;
int val[N][N];
int mx[N][N][][];
int mi[N][N][][]; void ST(int n,int m)
{
int i,j,r,c;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
mx[i][j][][]=mi[i][j][][]=val[i][j];
}
}
int kn=(int)(log(double(n))/log(2.0));
int km=(int)(log(double(m))/log(2.0));
for(i=;i<=kn;i++)
{
for(j=;j<=km;j++)
{
if(i== && j==) continue;
for(r=;r+(<<i)-<=n;r++)
{
for(c=;c+(<<j)-<=m;c++)
{
if(i==)
{
mx[r][c][i][j]=max(mx[r][c][i][j-],mx[r][c+(<<(j-))][i][j-]);
mi[r][c][i][j]=min(mi[r][c][i][j-],mi[r][c+(<<(j-))][i][j-]);
}
else
{
mx[r][c][i][j]=max(mx[r][c][i-][j],mx[r+(<<(i-))][c][i-][j]);
mi[r][c][i][j]=min(mi[r][c][i-][j],mi[r+(<<(i-))][c][i-][j]);
}
}
}
}
}
} int RMQ(int r1,int c1,int r2,int c2)
{
int kr=(int)(log(double(r2-r1+))/log(2.0));
int kc=(int)(log(double(c2-c1+))/log(2.0)); int t1=mx[r1][c1][kr][kc];
int t2=mx[r2-(<<kr)+][c1][kr][kc];
int t3=mx[r1][c2-(<<kc)+][kr][kc];
int t4=mx[r2-(<<kr)+][c2-(<<kc)+][kr][kc]; int m1=mi[r1][c1][kr][kc];
int m2=mi[r2-(<<kr)+][c1][kr][kc];
int m3=mi[r1][c2-(<<kc)+][kr][kc];
int m4=mi[r2-(<<kr)+][c2-(<<kc)+][kr][kc]; return max(max(t1,t2),max(t3,t4))-min(min(m1,m2),min(m3,m4));
} int main()
{
int i,j;
scanf("%d%d%d",&n,&b,&k);
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
scanf("%d",&val[i][j]);
}
}
ST(n,n);
while(k--)
{
int r1,c1,r2,c2;
scanf("%d%d",&r1,&c1);
r2=r1+b-;
c2=c1+b-;
printf("%d\n",RMQ(r1,c1,r2,c2));
}
return ;
}
正方形解法：
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
#define inf 0x7fffffff
#define N 255
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b int n,b,k;
int val[N][N];
int mx[N][N][];
int mi[N][N][]; int getMax(int x,int y,int p)
{
int res=-inf;
res=max(res,mx[x][y][p]);
if(x+(<<p)<=n) res=max(res,mx[x+(<<p)][y][p]);
if(y+(<<p)<=n) res=max(res,mx[x][y+(<<p)][p]);
if(x+(<<p)<=n && y+(<<p)<=n) res=max(res,mx[x+(<<p)][y+(<<p)][p]);
return res;
}
int getMin(int x,int y,int p)
{
int res=inf;
res=min(res,mi[x][y][p]);
if(x+(<<p)<=n) res=min(res,mi[x+(<<p)][y][p]);
if(y+(<<p)<=n) res=min(res,mi[x][y+(<<p)][p]);
if(x+(<<p)<=n && y+(<<p)<=n) res=min(res,mi[x+(<<p)][y+(<<p)][p]);
return res;
} void ST()
{
int i,j,k;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
mx[i][j][]=mi[i][j][]=val[i][j];
}
}
int kn=(int)(log(n*1.0)/log(2.0)); for(k=;k<=kn;k++)
{
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
mx[i][j][k]=getMax(i,j,k-);
mi[i][j][k]=getMin(i,j,k-);
}
}
}
} int RMQMAX(int x,int y,int b)
{
int p=(int)(log(b*1.0)/log(2.0));
int res=-inf;
res=max(res,mx[x][y][p]);
if(x+b-(<<p)<=n) res=max(res,mx[x+b-(<<p)][y][p]);
if(y+b-(<<p)<=n) res=max(res,mx[x][y+b-(<<p)][p]);
if(x+b-(<<p)<=n && y+b-(<<p)<=n) res=max(res,mx[x+b-(<<p)][y+b-(<<p)][p]);
return res;
} int RMQMIN(int x,int y,int b)
{
int p=(int)(log(b*1.0)/log(2.0));
int res=inf;
res=min(res,mi[x][y][p]);
if(x+b-(<<p)<=n) res=min(res,mi[x+b-(<<p)][y][p]);
if(y+b-(<<p)<=n) res=min(res,mi[x][y+b-(<<p)][p]);
if(x+b-(<<p)<=n && y+b-(<<p)<=n) res=min(res,mi[x+b-(<<p)][y+b-(<<p)][p]);
return res;
} int main()
{
int i,j;
scanf("%d%d%d",&n,&b,&k);
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
scanf("%d",&val[i][j]);
}
}
ST();
while(k--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",RMQMAX(x,y,b)-RMQMIN(x,y,b));
}
return ;
}