2859(ac).cpp

zoj的2859题。 2围的RMQ问题

//zoj 2859 二维RMQ
/*
RMQ问题以及ST(Sparse Table)算法


       RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。你当然可以写个O(n)的（怎么写都可以吧=_=),但是万一要询问最值1000000遍，估计你就要挂了。这时候你可以放心地写一个线段树（前提是不写错）O（logn)的复杂度应该不会挂。但是，这里有更牛的算法，就是ST算法，它可以做到O(nlogn)的预处理，O(1)！！！地回答每个询问。
       来看一下ST算法是怎么实现的(以最大值为例）：

       首先是预处理，用一个DP解决。设a[i]是要求区间最值的数列，f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把f[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段(长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i，j]就是这两段的最大值中的最大值。于是我们得到了动规方程F[i,j]=max（F[i，j-1],F[i+2^(j-1)，j-1]）.

接下来是得出最值，也许你想不到计算出f[i，j]有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n的区间（保证有f[i，j]对应）。直接给出表达式：
k:=ln(l(r-l+1)/ln(2));
ans:=max(F[l，k],F[r-2^k+1,k]);
这样就计算了从i开始，长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值（表达式比较烦琐，细节问题如加1减1需要仔细考虑
*/
/*
二维RMQ(Range Minimum Query)

先来看一维情形：
给定一个数组x以及大量的查询，查询内容是任意区间内的最小值，例如数组长度为n，则查询为从x[a]到x[b]中的最小值，0<=a<b<n, a, b 任意。
问题是如何进行预处理，使得每次查询时间为O(1)。

解法：计算出所有长度为2^i的区间的最小值，则任[a,b]区间可以拆为两个长度为2^i的区间的并集，i=log(b-a)。
例如查询1到100间的最小值，[1,64],[37,100]的最小值已知，则[1,100]的最小值，为这两者中的小者。
算法的空间和时间复杂度均为O(logN)

由此可以推演到二维情况，给一个n*n的矩阵，要查询任意子矩阵的最小值。
解法类似，计算出所有大小为2^i*2^j的子矩阵，然后查询时候，每个子矩阵可以看成是四个预处理矩阵的并集，查询时间仍然为O(1)，而预处理的复杂度为O(N*N*logN*lonN)

*/

/*
//一维 RMQ(Range Minimum/Maximum Query)  example:pku3368
//预处理O(nlogn) 查询O(1)
//下标从0开始
const int MAXN=100000+1;
const int MAXF=17;
const int INF=0x7FFFFFFF;
//可以断言 ceiil(log(MAXN,2))==MAXF

inline int max(int a,int b){return a>b?a:b;}

class{
    int dp[MAXN][MAXF+1];//dp[i][j]表示从a[i]起连续2^j次方个数的最大值
public:
    void init(int* a,int n){
        for(int i=0;i<n;i++){
            dp[i][0]=a[i];
        }
        for(int f=1,s=1;s<n;s=(1<<f++)){
            for(int i=0;i+s<n;i++){
                dp[i][f]=max(dp[i][f-1],dp[i+s][f-1]);
            }
        }
    }

    int query(int l,int r){
        if(l>r)return -INF;
        int d=r-l+1;
        int f;
        for(f=0;(1<<f)<=d;f++);
        f--;
        return max(dp[l][f],dp[r-(1<<f)+1][f]);
    }
}RMQ;
*/

#include<iostream>
#include<cstdio>

using namespace std;

int mat[310][310];
int table[9][9][310][310];
int n;
int b[] = {
 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
};

inline int minn(int a, int b)
{
 return a < b ? a : b;
}

int mylog(int n)
{
 if (n == 0)
  return 0;

 int i = 0;
 while (true) {
  if (n < b[i])
   return i - 1;
  ++i;
 }
 return -1;
}

void rmq()
{
 // 从小到大计算，保证后来用到的都已经计算过
 for(int i=0;i<=mylog(n);++i) // width
  for(int j=0;j<=mylog(n);++j){ //height
   if(i==0 && j==0)
    continue;
   for(int ii=0;ii+b[j]<=n;++ii)
    for(int jj=0;jj+b[i]<=n;++jj){
     if(i==0)
      table[i][j][ii][jj]=minn(table[i][j-1][ii][jj],table[i][j-1][ii+b[j-1]][jj]);
     else
      table[i][j][ii][jj]=minn(table[i-1][j][ii][jj],table[i-1][j][ii][jj+b[i-1]]);
    }
  }
}

int main()
{

 int T;
 cin >> T;
 while (T--) {
  cin >> n;
  for (int i = 0; i < n; ++i)
   for (int j = 0; j < n; ++j) {
    cin >> mat[i][j];
    table[0][0][i][j] = mat[i][j];
   }

   rmq();
   long N;
   cin >> N;
   int r1, c1, r2, c2;
   for (int i = 0; i < N; ++i) {
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    --r1;
    --c1;
    --r2;
    --c2;
    int w=mylog(c2-c1+1);
    int h=mylog(r2-r1+1);
    printf("%d\n",minn(table[w][h][r1][c1],minn(table[w][h][r1][c2-b[w]+1],minn(table[w][h][r2-b[h]+1][c1],table[w][h][r2-b[h]+1][c2-b[w]+1]))));
   }
 }

 return 0;
}