给定一个n*n的矩阵，有q次查询，每次查询一个子矩阵最小值
YY了一个n^2log(n)+n*q 的算法:建了n个一维RMQ，预处理n*n*log(n),每次查询复杂度O（n）,果断TLE
Google了一下才发现还有二维RMQ这种东西。。。
对代码用类封装了下。。。
RMQ_2D(O(n*n*log(n)*log(n)预处理，O(1)查询，查询以(x1,y1)，(x2,y2)为对角的矩形最小值)
class RMQ_2D
{
int dMin[MAXF][MAXF][MAXN][MAXN];
int pos[MAXN];
public:
void init(int a[][MAXN],int n,int m)
{
int i, j, u, v, b, c, d;
for( pos[0]= -1, i= 1; i<= n; ++i )
pos[i]= ( ( i& (i- 1) )== 0 )? pos[i- 1]+ 1: pos[i- 1];
for(u=1;u<=n;u++)
for(v=1;v<=m;v++)
dMin[0][0][u][v]=a[u][v];
for( i= 0; i<= pos[n]; ++i )
for( j= 0; j<= pos[m]; ++j )
for( u= 1; u<= n+ 1- (1<<i); u++ )
for( v= 1; v<= m+ 1- (1<<j); v++ )
{
if( i== 0 && j== 0 ) continue;
if( i== 0 ) dMin[i][j][u][v]= min( dMin[i][j- 1][u][v], dMin[i][j- 1][u][v+ (1<<(j- 1))] );
else dMin[i][j][u][v]= min( dMin[i- 1][j][u][v], dMin[i- 1][j][u+ (1<<(i- 1))][v] );
}
}
int query_min( int x1, int y1, int x2, int y2 )
{
int x= pos[x2- x1+ 1], y= pos[y2- y1+ 1];
int a= min( dMin[x][y][x1][y1], dMin[x][y][x2- (1<<x)+ 1][y1] );
int b= min( dMin[x][y][x1][y2- (1<<y)+ 1], dMin[x][y][x2- (1<<x)+ 1][y2- (1<<y)+ 1] );
return min(a,b);
}
};