http://acm.hdu.edu.cn/showproblem.php?pid=2888
模板题 直接用二维rmq
读入数据时比较坑爹 cin 会超时
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 const int maxn = 305; 7 8 int N, M, Q, g[maxn][maxn], dp[maxn][maxn][9][9]; 9 10 void rmq_init(int n, int m) { 11 for (int i = 1; i <= n; i++) { 12 for (int j = 1; j <= m; j++) 13 dp[i][j][0][0] = g[i][j]; 14 } 15 16 for (int x = 0; (1<<x) <= n; x++) 17 for (int y = 0; (1<<y) <= m; y++) 18 if (x + y) 19 for (int i = 1; i + (1<<x) - 1 <= n; i++) 20 for (int j = 1; j + (1<<y) - 1 <= m; j++) { 21 if (x) 22 dp[i][j][x][y] = max(dp[i][j][x-1][y], dp[i+(1<<(x-1))][j][x-1][y]); 23 else 24 dp[i][j][x][y] = max(dp[i][j][x][y-1], dp[i][j+(1<<(y-1))][x][y-1]); 25 } 26 } 27 28 int rmq_query(int x1, int y1, int x2, int y2) { 29 int x = 0, y = 0; 30 while ((1<<(x+1)) <= x2 - x1 + 1) x++; 31 while ((1<<(y+1)) <= y2 - y1 + 1) y++; 32 x2 = x2 - (1<<x) + 1; 33 y2 = y2 - (1<<y) + 1; 34 35 return max( max(dp[x1][y1][x][y], dp[x2][y1][x][y]), max(dp[x1][y2][x][y], dp[x2][y2][x][y])); 36 } 37 38 int main () { 39 while (scanf("%d%d", &N, &M) == 2) { 40 for (int i = 1; i <= N; i++) { 41 for (int j = 1; j <= M; j++) 42 scanf("%d", &g[i][j]); 43 } 44 rmq_init(N, M); 45 46 scanf("%d", &Q); 47 int x1, y1, x2, y2; 48 while (Q--) { 49 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 50 int ans = rmq_query(x1, y1, x2, y2); 51 bool flag = false; 52 if (ans == g[x1][y1] || ans == g[x1][y2] || ans == g[x2][y1] || ans == g[x2][y2]) 53 flag = true; 54 printf("%d %s ", ans, flag ? "yes" : "no"); 55 } 56 } 57 return 0; 58 }