hdu 2888 check corners (二维rmq模板题)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年05月16日 星期一 16时51分00秒
  4File Name :code/hdu/2888.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=301;
 34int n,m,q;
 35int a[N][N];
 36int dp[N][N][9][9];
 37
 38
 39void init_rmq()
 40{
 41    for ( int i = 1 ; i <= n ; i++)
 42	for ( int j = 1; j <= m ; j++) dp[i][j][0][0] = a[i][j];
 43
 44    for ( int i = 0 ; (1<<i)<= n ; i++)
 45	for ( int j = 0 ; (1<<j)<= m  ;j++)
 46	    if (i==0&&j==0) continue;
 47	    else for ( int p = 1 ; p + (1<<i)-1 <= n ; p++)
 48		      for ( int q = 1 ; q + (1<<j)-1 <= m ;q ++)
 49			  if (i==0)
 50			      dp[p][q][i][j] = max(dp[p][q][i][j-1],dp[p][q+(1<<(j-1))][i][j-1]);
 51			  else dp[p][q][i][j] = max(dp[p][q][i-1][j],dp[p+(1<<(i-1))][q][i-1][j]);
 52
 53}
 54
 55
 56
 57int rmq_max(int x1,int y1,int x2,int y2)
 58{
 59    int k1 = 0 ;
 60    int k2 = 0 ;
 61
 62    while (1<<(k1+1)<=x2-x1+1) k1++;
 63    while (1<<(k2+1)<=y2-y1+1) k2++;
 64
 65    int tmp1 = dp[x1][y1][k1][k2];
 66    int tmp2 = dp[x2-(1<<k1)+1][y1][k1][k2];
 67    int tmp3 = dp[x1][y2-(1<<k2)+1][k1][k2];
 68    int tmp4 = dp[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2];
 69
 70    return max(max(tmp1,tmp2),max(tmp3,tmp4));
 71}
 72
 73int main()
 74{
 75	#ifndef  ONLINE_JUDGE 
 76	freopen("code/in.txt","r",stdin);
 77  #endif
 78
 79	while (scanf("%d %d",&n,&m)!=EOF)
 80	{
 81	    for ( int i = 1 ; i <= n ; i++)
 82		for ( int j = 1 ; j <= m ; j++) scanf("%d",&a[i][j]);
 83	    init_rmq();
 84
 85	    scanf("%d",&q);
 86	    while (q--)
 87	    {
 88		int r1,c1,r2,c2;
 89		scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
 90		int ans = rmq_max(r1,c1,r2,c2);
 91		printf("%d ",ans);
 92		if (a[r1][c1]==ans||a[r1][c2]==ans||a[r2][c1]==ans||a[r2][c2]==ans)
 93		{
 94		    puts("yes");
 95		}
 96		else
 97		{
 98		    puts("no");
 99		}
100	    }
101
102	}
103
104
105
106  #ifndef ONLINE_JUDGE  
107  fclose(stdin);
108  #endif
109    return 0;
110}