Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：问某个矩阵内的最大值，并且问最大值是否是在四个角中出现。 思路：二维rmq.需要注意数组稍微开大1就会MLE，因为是四维数组，一维大一点，整个就会大很多==。
代码实现
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}