和hdu2888基本上一样的，也是求一个矩阵内的极值
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 252 int n,b,q; int dpmax[maxn][maxn][9][9],dpmin[maxn][maxn][9][9],val[maxn][maxn]; void ST(){ int k=log2(n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dpmax[i][j][0][0]=dpmin[i][j][0][0]=val[i][j]; for(int i=0;i<=k;i++)//先求出一行内的最大值和最小值，然后再求出行间的最大值和最小值 for(int j=0;j<=k;j++){ if(i==0 && j==0) continue; for(int r=1;r+(1<<i)-1<=n;r++) for(int c=1;c+(1<<j)-1<=n;c++) if(i==0){//在同一行内 dpmax[r][c][i][j]=max(dpmax[r][c][i][j-1],dpmax[r][c+(1<<(j-1))][i][j-1]); dpmin[r][c][i][j]=min(dpmin[r][c][i][j-1],dpmin[r][c+(1<<(j-1))][i][j-1]); } else { dpmax[r][c][i][j]=max(dpmax[r][c][i-1][j],dpmax[r+(1<<(i-1))][c][i-1][j]); dpmin[r][c][i][j]=min(dpmin[r][c][i-1][j],dpmin[r+(1<<(i-1))][c][i-1][j]); } } } int query(int r,int c){ int r1=r,c1=c,r2=r+b-1,c2=c+b-1,k=log2(b); int max1=dpmax[r1][c1][k][k]; int max2=dpmax[r2-(1<<k)+1][c1][k][k]; int max3=dpmax[r1][c2-(1<<k)+1][k][k]; int max4=dpmax[r2-(1<<k)+1][c2-(1<<k)+1][k][k]; int min1=dpmin[r1][c1][k][k]; int min2=dpmin[r2-(1<<k)+1][c1][k][k]; int min3=dpmin[r1][c2-(1<<k)+1][k][k]; int min4=dpmin[r2-(1<<k)+1][c2-(1<<k)+1][k][k]; return max(max(max1,max2),max(max3,max4))-min(min(min1,min2),min(min3,min4)); } int main(){ while(scanf("%d%d%d",&n,&b,&q)==3){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&val[i][j]); ST();int r,c; while(q--){ scanf("%d%d",&r,&c); printf("%d ",query(r,c)); } } return 0; }