hdu2888(2).cpp

//#include <bits/stdc++.h>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#define PI 3.14159265
#define N 300+5
#define ll long long
#define INF 2147483647
using namespace std;
int dp[N][N][9][9];//dp[i][j][mi][mj]分別代表:行的前標,列的前標,log(2)行的數組塊長,log(2)列的數組塊長
int g[N][N],n,x1,Y1,x2,y2,m,nq,maxi,from,to,m1,m2,m3,m4;

void build(){
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) dp[i][j][0][0]=g[i][j];//1x1的ij矩陣 max=自己
    for(int mi=0;mi<=log2(n);mi++)//跟一維RMQ不同的是 這裡長度從2^0開始算 因為可以出現行長度為1 而列長度不為1的情況
        for(int mj=0;mj<=log2(m);mj++){
            if(!(mi+mj)) continue;
            for(int i=0;i+(1<<mi)-1<n;i++)
                for(int j=0;j+(1<<mj)-1<m;j++){
                    if(mi==0) //每行：長度唯為1時,單純求一列的RMQ(當作一維陣列）
                        dp[i][j][mi][mj]=max(dp[i][j][mi][mj-1],dp[i][j+(1<<(mj-1))][mi][mj-1]);
                    else //每列：做全部的累積加總
                        dp[i][j][mi][mj]=max(dp[i][j][mi-1][mj],dp[i+(1<<(mi-1))][j][mi-1][mj]);
                }
        }
}
int RMQ_2D(int x1,int Y1,int x2,int y2){
    if(x1>x2) swap(x1,x2);
    if(Y1>y2) swap(Y1,y2);
    int mi=log2(x2-x1+1), mj=log2(y2-Y1+1);
    m1=dp[x1][Y1][mi][mj];
    m2=dp[x2-(1<<mi)+1][Y1][mi][mj];
    m3=dp[x1][y2-(1<<mj)+1][mi][mj];
    m4=dp[x2-(1<<mi)+1][y2-(1<<mj)+1][mi][mj];
    return max(max(m1,m2),max(m3,m4)); //max(max(m1,m2),max(m1,m3),max(m2,m4),max(m3,m4))的簡化版
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) scanf("%d",&g[i][j]);
        build();
        scanf("%d",&nq);
        while(nq--){
            scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
            x1--; Y1--; x2--; y2--;
            maxi=RMQ_2D(x1,Y1,x2,y2);
            if(g[x1][Y1]==maxi||g[x1][y2]==maxi||g[x2][Y1]==maxi||g[x2][y2]==maxi)
                printf("%d yes\n",maxi);
            else printf("%d no\n",maxi);
        }
    }
}