| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 7444 | Accepted: 3609 |
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
Source
- 二维区间最值RMQ
- 用二维ST表即可
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL ;
typedef unsigned long long ULL ;
const int maxn = 1e5 + ;
const int inf = 0x3f3f3f3f ;
const int npos = - ;
const int mod = 1e9 + ;
const int mxx = + ;
const double eps = 1e- ;
const double PI = acos(-1.0) ; int max4(int a, int b, int c, int d){
return max(max(a,b),max(c,d));
}
int min4(int a, int b, int c, int d){
return min(min(a,b),min(c,d));
}
int mx[][][][], mi[][][][], fac[];
int RMQmx(int x1, int y1, int x2, int y2, int m){
int k=(int)(log((double)m)/log(2.0));
return max4(mx[x1][y1][k][k],mx[x1][y2-fac[k]+][k][k],mx[x2-fac[k]+][y1][k][k],mx[x2-fac[k]+][y2-fac[k]+][k][k]);
}
int RMQmi(int x1, int y1, int x2, int y2, int m){
int k=(int)(log((double)m)/log(2.0));
return min4(mi[x1][y1][k][k],mi[x1][y2-fac[k]+][k][k],mi[x2-fac[k]+][y1][k][k],mi[x2-fac[k]+][y2-fac[k]+][k][k]);
}
int n, m, q, t, u, v;
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
for(int i=;i<;i++)
fac[i]=(<<i);
while(~scanf("%d %d %d",&n,&m,&q)){
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
scanf("%d",&t);
mx[i][j][][]=t;
mi[i][j][][]=t;
}
int k=(int)(log((double)n)/log(2.0));
// [x][y][1<<e][1<<f]
for(int e=;e<=k;e++)
for(int f=;f<=k;f++)
for(int i=;i+fac[e]-<=n;i++)
for(int j=;j+fac[f]-<=n;j++){
mx[i][j][e][f]=max4(mx[i][j][e-][f-],mx[i+fac[e-]][j][e-][f-],mx[i][j+fac[f-]][e-][f-],mx[i+fac[e-]][j+fac[f-]][e-][f-]);
mi[i][j][e][f]=min4(mi[i][j][e-][f-],mi[i+fac[e-]][j][e-][f-],mi[i][j+fac[f-]][e-][f-],mi[i+fac[e-]][j+fac[f-]][e-][f-]);
}
while(q--){
scanf("%d %d",&u,&v);
printf("%d\n",RMQmx(u,v,u+m-,v+m-,m)-RMQmi(u,v,u+m-,v+m-,m));
}
}
return ;
}