预处理时间复杂度为 O(NlogN)，查找时间复杂度为 O(1)
/*The RMQ question, using Sparse Table(ST) algorithm to solve it *http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor * *initRMQ: M[N][logN][N][logN], i,j,u,v * j: from 0 to logN (2^j <= N) * v: from 0 to logN (2^v <= N) * i: from 0 to N-1 (i+2^j-1 < N) * u: from o to N-1 (u+2^v-1 < N) * M[i][j][u][v] = 1) matrix[i][u], if j==0&&v==0; * 2) min(M[i][j-1][u][v], M[i+(2^(j-1))][j-1][u][v]), if v==0 * 3) min(M[i][j][u][v-1], M[i][j][u+(2^(v-1))][v-1]), else */ #include <stdio.h> #define min(a,b) (((a)<(b))?(a):(b)) #define N 310 int matrix[N][N]; int M[N][9][N][9]; int log_2(int n) { int pos = -1, i = 1; while(i <= n) { if( (i&(i-1)) == 0) pos += 1; i++; } return pos; } void initRMQ(int n) { int i, j, u, v; int logn = log_2(n); for(j = 0; j <= logn; j++) for(v = 0; v <= logn; v++) for(i = 0; i+(1<<j)-1 < n; i++) /*i+(1<<j)-1 < n*/ for(u = 0; u+(1<<v)-1 < n; u++) /*u+(1<<v)-1 < n*/ { if(j == 0 && v == 0) { M[i][j][u][v] = matrix[i][u]; } else if(v == 0) { M[i][j][u][v] = min(M[i][j-1][u][v], M[i+(1<<(j-1))][j-1][u][v]); } else { M[i][j][u][v] = min(M[i][j][u][v-1], M[i][j][u+(1<<(v-1))][v-1]); } } } int askRMQ(int i, int j, int u, int v) { int k = log_2(u-i+1); int t = log_2(v-j+1); int a = min(M[i][k][j][t], M[i][k][v-(1<<t)+1][t]); int b = min(M[u-(1<<k)+1][k][j][t], M[u-(1<<k)+1][k][v-(1<<t)+1][t]); return min(a,b); } int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); int i, j; for(i = 0; i < n; i++) for(j = 0; j < n; j++) scanf("%d", &(matrix[i][j])); initRMQ(n); int queries; scanf("%d", &queries); while(queries--) { int r1, c1, r2, c2; scanf("%d%d%d%d", &r1, &c1, &r2, &c2); printf("%d\n", askRMQ(r1-1, c1-1, r2-1, c2-1)); } } return 0; }
参考算法：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor