題目大意： 給定一個 N*N 的數組 ? 求以（x1， y1） 為左上角 ?（x1 + b -1 ，y1 + b -1)為右下角 這個b*b的范圍內最大值減最小值

看到最大值最小值當然想到RMQ啦

View Code //Accepted 27392K 594MS C++ 2416B #include <iostream> #include <stdio.h> #include <cmath> using namespace std; const int maxn = 301; int N; int val[maxn][maxn]; int st_min[maxn][maxn][9][9]; int st_max[maxn][maxn][9][9]; inline int minn(int a,int b){ return a>b?b:a; } inline int maxx(int a,int b){ return a>b?a:b; } void RMQ_2D_PRE() {for(int row = 1; row <= N; row++)for(int col = 1; col<=N; col++){st_min[row][col][0][0] = val[row][col];st_max[row][col][0][0] = val[row][col];}int m = log(double(N)) / log(2.0);for(int i=0; i<=m; i++)for(int j=0; j<=m; j++){if(i == 0 && j==0)continue;for(int row = 1; row+(1<<i)-1 <= N; row++)for(int col = 1; col+(1<<j)-1 <= N; col++){if(i == 0){st_min[row][col][i][j] = minn(st_min[row][col][i][j-1] , st_min[row][col+(1<<(j-1))][i][j-1]); //水平劃分st_max[row][col][i][j] = maxx(st_max[row][col][i][j-1] , st_max[row][col+(1<<(j-1))][i][j-1]); //水平劃分 }else{st_min[row][col][i][j] = minn(st_min[row][col][i-1][j] , st_min[row+(1<<(i-1))][col][i-1][j]); //豎直劃分st_max[row][col][i][j] = maxx(st_max[row][col][i-1][j] , st_max[row+(1<<(i-1))][col][i-1][j]); //豎直劃分 }}} } int RMQ_2D_min(int x1,int x2,int y1,int y2) {int kx = log(double(x2 - x1 +1)) / log(2.0);int ky = log(double(y2 - y1 +1)) / log(2.0);int m1 = st_min[x1][y1][kx][ky];int m2 = st_min[x2-(1<<kx)+1][y1][kx][ky];int m3 = st_min[x1][y2-(1<<ky)+1][kx][ky];int m4 = st_min[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky];return minn( minn(m1,m2), minn(m3,m4) );} int RMQ_2D_max(int x1,int x2,int y1,int y2) {int kx = log(double(x2 - x1 +1)) / log(2.0);int ky = log(double(y2 - y1 +1)) / log(2.0);int m1 = st_max[x1][y1][kx][ky];int m2 = st_max[x2-(1<<kx)+1][y1][kx][ky];int m3 = st_max[x1][y2-(1<<ky)+1][kx][ky];int m4 = st_max[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky];return maxx( maxx(m1,m2), maxx(m3,m4) );} int main(void) {int M,B;int x1,y1;while(scanf("%d%d%d",&N,&B,&M)!=EOF){ for(int i=1; i<=N; i++)for(int j=1; j<=N; j++)scanf("%d",&val[i][j]); RMQ_2D_PRE(); while(M--){scanf("%d%d",&x1,&y1); printf("%d\n",RMQ_2D_max(x1,x1+B-1,y1,y1+B-1)-RMQ_2D_min(x1,x1+B-1,y1,y1+B-1));}}return 0; }

轉載于:https://www.cnblogs.com/asen32/archive/2012/08/22/2651495.html

總結

以上是生活随笔為你收集整理的poj--2019 Cornfields 2维RMQ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。