二维RMQ模板

const int maxn=100+7; int n,m; int dp[maxn][maxn][10][10],val[maxn][maxn]; void init() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { //scanf("%d", &val[i][j]); dp[i][j][0][0] = val[i][j]; printf("val[%d][%d]=%d\n",i,j,val[i][j]); } } for (int i = 0; (1 << i) <= n; i++) { for (int j = 0; (1 << j) <= m; j++) { if (i == 0 && j == 0) continue; for (int row = 1; row + (1 << i) - 1 <= n; row++) { for (int col = 1; col + (1 << j) - 1 <= m; col++) { if (i == 0) dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]); else if (j == 0) dp[row][col][i][j] = max(dp[row][col][i - 1][j], dp[row + (1 << (i - 1))][col][i - 1][j]); else dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]); } } } } } int Query(int x1, int y1, int x2, int y2) { int kx = 0, ky = 0; while (x1 + (1 << (1 + kx)) - 1 <= x2) kx++; while (y1 + (1 << (1 + ky)) - 1 <= y2) ky++; int m1 = dp[x1][y1][kx][ky]; int m2 = dp[x2 - (1 << kx) + 1][y1][kx][ky]; int m3 = dp[x1][y2 - (1 << ky) + 1][kx][ky]; int m4 = dp[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky]; return max(max(m1, m2), max(m3, m4)); }