hdu2888.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 st[N][N][9];//2^9>300
int g[N][N],n,x1,Y1,x2,y2,m,level,nq,maxi,from,to;

void RMQ2d(int x1,int Y1,int x2,int y2){
    if(x1>x2) swap(x1,x2);
    from=min(Y1,y2);
    to=max(Y1,y2);
    level=log2(to-from+1);
    maxi=-9999;
    for(int i=x1;i<=x2;i++) maxi=max(maxi,max(st[i][from][level],st[i][to+1-(1<<level)][level]));//這裡不能從from加 要用to減是因為要分割的數組塊長度可能為奇數 且st[][]只記錄前標及長度 所以會出錯 例如分割1234567 錯的：1234 5678 對的：1234 4567
}
void build(){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) st[i][j][0]=g[i][j];
        for(int level=1;level<=log2(m);level++)
            for(int from=0;from+(1<<(level-1))-1<m;from++){//因為數組長最短=1 所以前標最大為from+(1<<(level-1))-1
                st[i][from][level]=max(st[i][from][level-1],st[i][from+(1<<(level-1))][level-1]);
            }
    }
}
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--;
            RMQ2d(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);
        }
    }
}