hduacm 2888 ----二维rmq

http://acm.hdu.edu.cn/showproblem.php?pid=2888

模板题  直接用二维rmq

读入数据时比较坑爹  cin 会超时

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int N, M, Q, g[maxn][maxn], dp[maxn][maxn][][];

 void rmq_init(int n, int m) {

     for (int i = ; i <= n; i++) {

         for (int j = ; j <= m; j++)

             dp[i][j][][] = g[i][j];

     }

     for (int x = ; (<<x) <= n; x++)

         for (int y = ; (<<y) <= m; y++)

             if (x + y)

                 for (int i = ; i + (<<x) -  <= n; i++)

                     for (int j = ; j + (<<y) -  <= m; j++) {

                         if (x)

                             dp[i][j][x][y] = max(dp[i][j][x-][y], dp[i+(<<(x-))][j][x-][y]);

                         else

                             dp[i][j][x][y] = max(dp[i][j][x][y-], dp[i][j+(<<(y-))][x][y-]);

                     }

 }

 int rmq_query(int x1, int y1, int x2, int y2) {

     int x = , y = ;

     while ((<<(x+)) <= x2 - x1 + ) x++;

     while ((<<(y+)) <= y2 - y1 + ) y++;

     x2 = x2 - (<<x) + ;

     y2 = y2 - (<<y) + ;

     return max( max(dp[x1][y1][x][y], dp[x2][y1][x][y]), max(dp[x1][y2][x][y], dp[x2][y2][x][y]));

 }

 int main () {

     while (scanf("%d%d", &N, &M) == ) {

         for (int i = ; i <= N; i++) {

             for (int j = ; j <= M; j++)

                 scanf("%d", &g[i][j]);

         }

         rmq_init(N, M);

         scanf("%d", &Q);

         int x1, y1, x2, y2;

         while (Q--) {

             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

             int ans = rmq_query(x1, y1, x2, y2);

             bool flag = false;

             if (ans == g[x1][y1] || ans == g[x1][y2] || ans == g[x2][y1] || ans == g[x2][y2])

                 flag = true;

             printf("%d %s\n", ans, flag ? "yes" : "no");

         }

     }

     return ;

 }