题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2888
题目大意：给定一个n
* m的矩阵，再给定q个询问，每次询问(r1，c1)为左上角，(r2,c2)为右下角的子矩形的最大值。
解题思路：很常规的二维RMQ查询最大值。第一次写二维rmq，现在来理下思路。
二维RMQ是一维RMQ的简单拓展，从一维变成二维，时空复杂度都变高了，但核心思想思想不变，都是倍增的思想。
构造RMQ数组 Create(int n,int m,int b[][]) O(n*m*log(n)*log(m))算法复杂度
dp[row][col][i][j] 表示 行从row ->row +2^i-1 列从col ->col +2^j-1 二维区间里最大值
dp[row][col][i][j] = 下行
max{dp[row][col][i][j-1],dp[row][col][i-1][j],dp[row][col+2^(j-1)][i][j-1],dp[row+2^(i-1)][col][i-1][j]}
查询RMQ rmq(int sx,int ex,int sy,int ey)
同一维的将sx->ex 分为两个2^kx区间 将 sy->ey分为两个2^ky的区间
kx=(int)log2(ex-sx+1) ky=(int)log2(ey-sy+1)
查询结果为
max{dp[sx][sy][kx][ky],dp[sx][ey-2^ky+1][kx][ky],dp[ex-2^kx+1][sy][kx][ky],dp[ex-2^kx+1][ey-2^ky+1][kx][ky]}
测试数据：
4 4
4 4 10 7
2 13 9 11
5 7 8 20
13 20 8 2
4
1 1 4 4
1 1 3 3
1 3 3 4
1 1 1 1
C艹代码：
- #include <stdio.h>
- #include <string.h>
- #define MAX 301
- #define max(a,b) ((a)>(b)?(a):(b))
- int flag,power[MAX];
- int n,m,q,arr[MAX][MAX];
- struct RMQ{
- int dp[MAX][MAX][9][9];
- void Create();
- int Query(int rowl,int rowr,int col,int cor);
- }rmq;
- void RMQ::Create() {
- int i,j,k,s,limitn,limitm;
- for (i = 1; i <= n; ++i)
- for (j = 1; j <= m; ++j)
- dp[i][j][0][0] = arr[i][j];
- for (i = 0; i <= power[n]; ++i)
- for (j = 0; j <= power[m]; ++j) {
- if (i == 0 && j == 0) continue;
- limitn = n + 1 - (1<<i);
- limitm = m + 1 - (1<<j);
- for (k = 1; k <= limitn; ++k)
- for (s = 1; s <= limitm; ++s) {
- if (i == 0)
- dp[k][s][i][j] = max(dp[k][s][i][j-1],dp[k][s+(1<<(j-1))][i][j-1]);
- else
- dp[k][s][i][j] = max(dp[k][s][i-1][j],dp[k+(1<<(i-1))][s][i-1][j]);
- }
- }
- }
- int RMQ::Query(int r1, int r2, int c1, int c2) {
- int temp = 0;
- int rk = power[r2-r1+1];
- int ck = power[c2-c1+1];
- temp = max(temp,dp[r1][c1][rk][ck]);
- temp = max(temp,dp[r1][c2-(1<<ck)+1][rk][ck]);
- temp = max(temp,dp[r2-(1<<rk)+1][c1][rk][ck]);
- temp = max(temp,dp[r2-(1<<rk)+1][c2-(1<<ck)+1][rk][ck]);
- if (temp == arr[r1][c1] || temp == arr[r2][c1]
- || temp == arr[r1][c2] || temp == arr[r2][c2])
- flag = 1;
- return temp;
- }
- void input (int &a) {
- char c, f;
- while (((c = getchar()) < '0' || f > '9') );
- for (a = 0; c >= '0' && c <= '9'; c = getchar())a = a * 10 + c - '0';
- }
- int main()
- {
- int i,j,k = 0;
- int t,a,b,c,d;
- for (i = 1; i <= 300; ++i)
- if (i < (1<<k)) power[i] = k - 1;
- else power[i] = k,k++;
- while (scanf("%d%d",&n,&m) != EOF) {
- for (i = 1; i <= n; ++i)
- for (j = 1; j <= m; ++j)
- input(arr[i][j]);//scanf("%d",&arr[i][j]);
- rmq.Create();
- //scanf("%d",&q);
- input(q);
- while (q--) {
- input(a),input(b);
- input(c),input(d);
- //scanf("%d%d%d%d",&a,&b,&c,&d);
- flag = 0;
- k = rmq.Query(a,c,b,d);
- if (flag) printf("%d yes\n",k);
- else printf("%d no\n",k);
- }
- }
- }