二维RMQ
题意：给一个n*m的矩阵，下面q的询问，每个询问给出一个子矩阵的左上角和右下角的坐标，要你求出这个子矩阵里面的最大元素，然后输出，并且，这个最大元素和子矩阵的四个角上的元素比较，只要能和其中一个元素相等，就输出yes，否则输出no
一维RMQ的ST算法，是叫一段2^i长度的序列分成两个2^(i-1)的序列然后计算。二维的RMQ依然使用ST的DP思想，不过对于一个矩形，将其分成完全相等的4个部分，然后求最值，特殊情况是，当一个子矩阵的宽为1，即在宽上不能二分的时候，已经长为1，即长不能二分的时候，其实就是一个一维的RMQ，我是采用了单独处理的方法（我把它归为初始化的一部分），而对于一般情况，就是普通的DP了
查询也是一样的，和一维的查询思想相同，也是将要查询的矩阵分成4份，允许有覆盖部分的去查询
思想不难的，代码量多了而已，注意细节，另外空间比较那个，会超空间，只要数组在够用的情况下尽可能小就可以了
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define N 305 #define M 11 #define INF 0x3f3f3f3f int row,col; int __pow[M]; int dp[N][M][N][M]; int a[N][N]; bool check(int res , int r1 , int c1 , int r2 , int c2) { if(res == a[r1][c1] || res == a[r1][c2] || res == a[r2][c1] || res == a[r2][c2]) return true; return false; } inline int max(int aa ,int bb ,int cc ,int dd) { int res = -INF; res = aa > res ? aa : res; res = bb > res ? bb : res; res = cc > res ? cc : res; res = dd > res ? dd : res; return res; } void ST() { int KR = (int)(log((double)row) / log(2.0)); int KC = (int)(log((double)col) / log(2.0)); for(int i=1; i<=row; i++) //初始化dp[i][0][j][0] for(int j=1; j<=col; j++) dp[i][0][j][0] = a[i][j]; for(int i=1; i<=row; i++) //初始化dp[i][0][j][p] for(int pc=1; pc<=KC; pc++) for(int j=1; j+__pow[pc]-1<=col; j++) { int kc = j + __pow[pc-1]; int x = dp[i][0][j][pc-1] , y = dp[i][0][kc][pc-1]; dp[i][0][j][pc] = x > y ? x : y; } for(int j=1; j<=col; j++) //初始化dp[i][p][j][0] for(int pr=1; pr<=KR; pr++) for(int i=1; i+__pow[pr]-1<=row; i++) { int kr = i + __pow[pr-1]; int x = dp[i][pr-1][j][0] , y = dp[kr][pr-1][j][0]; dp[i][pr][j][0] = x > y ? x : y; } for(int pr=1; pr<=KR; pr++) for(int pc=1; pc<=KC; pc++) for(int i=1; i+__pow[pr]-1<=row; i++) for(int j=1; j+__pow[pc]-1<=col; j++) { int kr = i + __pow[pr-1]; int kc = j + __pow[pc-1]; dp[i][pr][j][pc] = max(dp[i][pr-1][j][pc-1] , dp[i][pr-1][kc][pc-1] , dp[kr][pr-1][j][pc-1] , dp[kr][pr-1][kc][pc-1]); } } int RMQ(int r1 , int c1 , int r2 , int c2) { int KR = (int)(log((double)(r2-r1+1)) / log(2.0)); int KC = (int)(log((double)(c2-c1+1)) / log(2.0)); int kr = r2 - __pow[KR] + 1; int kc = c2 - __pow[KC] + 1; return max(dp[r1][KR][c1][KC] , dp[r1][KR][kc][KC] , dp[kr][KR][c1][KC] , dp[kr][KR][kc][KC]); } int main() { for(int i=0; i<M; i++) __pow[i] = (1<<i); while(scanf("%d%d",&row,&col)!=EOF) { for(int i=1; i<=row; i++) for(int j=1; j<=col; j++) scanf("%d",&a[i][j]); ST(); int q; scanf("%d",&q); while(q--) { int ok = 0,r1,c1,r2,c2; scanf("%d%d%d%d",&r1,&c1,&r2,&c2); int res = RMQ(r1,c1,r2,c2); printf("%d ",res); if(check(res ,r1,c1,r2,c2)) printf("yes\n"); else printf("no\n"); } } return 0; }