题目
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 5032 | Accepted: 2452 |
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
代码示例
感谢邝斌大神的模板~http://www.cnblogs.com/kuangbin/
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int val[255][255]; int mm[255]; int dpmin[255][255][8][8];//最小值 int dpmax[255][255][8][8];//最大值 void initRMQ(int n,int m) { for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) dpmin[i][j][0][0] = dpmax[i][j][0][0] = val[i][j]; for(int ii = 0; ii <= mm[n]; ii++) for(int jj = 0; jj <= mm[m]; jj++) if(ii+jj) for(int i = 1; i + (1<<ii) - 1 <= n; i++) for(int j = 1; j + (1<<jj) - 1 <= m; j++){ if(ii){ dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-1][jj],dpmin[i+(1<<(ii-1))][j][ii-1][jj]); dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-1][jj],dpmax[i+(1<<(ii-1))][j][ii-1][jj]); } else{ dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-1],dpmin[i][j+(1<<(jj-1))][ii][jj-1]); dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-1],dpmax[i][j+(1<<(jj-1))][ii][jj-1]); } } } //查询矩形的最大值 int rmq1(int x1,int y1,int x2,int y2){ int k1 = mm[x2-x1+1]; int k2 = mm[y2-y1+1]; x2 = x2 - (1<<k1) + 1; y2 = y2 - (1<<k2) + 1; return max(max(dpmax[x1][y1][k1][k2],dpmax[x1][y2][k1][k2]),max(dpmax[x2][y1][k1][k2],dpmax[x2][y2][k1][k2])); } //查询矩形的最小值 int rmq2(int x1,int y1,int x2,int y2){ int k1 = mm[x2-x1+1]; int k2 = mm[y2-y1+1]; x2 = x2 - (1<<k1) + 1; y2 = y2 - (1<<k2) + 1; return min(min(dpmin[x1][y1][k1][k2],dpmin[x1][y2][k1][k2]),min(dpmin[x2][y1][k1][k2],dpmin[x2][y2][k1][k2])); } int main(){ mm[0] = -1; for(int i = 1;i <= 500;i++) mm[i] = ((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; int N,B,K; while(scanf("%d%d%d",&N,&B,&K)==3){ for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++) scanf("%d",&val[i][j]); initRMQ(N,N); int x,y; while(K--){ scanf("%d%d",&x,&y); printf("%d\n",rmq1(x,y,x+B-1,y+B-1)-rmq2(x,y,x+B-1,y+B-1)); } } return 0; }