[poj2019]Cornfields(二维RMQ)

题意：给你一个n*n的矩阵，让你从中圈定一个小矩阵，其大小为b*b，有q个询问，每次询问告诉你小矩阵的左上角，求小矩阵内的最大值和最小值的差。

解题关键：二维st表模板题。

预处理复杂度：$O({n^2}\log n)$

查询复杂度：$O(n)$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<iostream>

 #include<cmath>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long ll;

 int arr[][];

 int max1[][][],min1[][][];

 int n,b,k;

 void rmq_init(int n){

     int lg=int(log(n)/log());

     for(int i=;i<=n;i++){

         for(int j=;j<=n;j++){

             max1[i][j][]=min1[i][j][]=arr[i][j];

         }

     }

     for(int i=;i<=n;i++){

         for(int j=;j<=lg;j++){

             for(int k=;k<=n;k++){

                 max1[i][k][j]=max(max1[i][k][j-],max1[i][k+(<<(j-))][j-]);

                 min1[i][k][j]=min(min1[i][k][j-],min1[i][k+(<<(j-))][j-]);

             }

         }

     }

 }

 int query(int x,int y){

     int k=int(log(b)/log(2.0));

     int maxd=-inf,mind=inf,tmp1,tmp2,yr=y+b-;

     for(int i=x;i<=x+b-;i++){

         tmp1=max(max1[i][y][k],max1[i][yr-(<<k)+][k]);//k询问时就不需要再减1了

         tmp2=min(min1[i][y][k],min1[i][yr-(<<k)+][k]);

         maxd=max(tmp1,maxd);

         mind=min(tmp2,mind);

     }

     return maxd-mind;

 }

 int main(){

     ios::sync_with_stdio();

     while(cin>>n>>b>>k){

         for(int i=;i<=n;i++){

             for(int j=;j<=n;j++){

                 cin>>arr[i][j];

             }

         }

         rmq_init(n);

         int a,b;

         while(k--){

             cin>>a>>b;

             int ans=query(a,b);

             cout<<ans<<"\n";

         }

     }

     return ;

 }