P2216 [HAOI2007]理想的正方形（二维st表）

考虑一下一维情况,似乎只是一个RMQ问题。一维情况下,就是考虑找出一个区间长度固定的一个区间,对应 m x − m i n mx-min mx−min最小即可. 在二维的情况,考虑枚举该正方形的左上角,需要一个数据结构支持查询二维的一个最大值. 考虑 s t st st表来实现这个功能,因为查询比较多而且是静态的. 然后该 s t st st表是一个二维形式呈现的. m x ( i , j , k ) : mx(i,j,k): mx(i,j,k):以 ( i , j ) (i,j) (i,j)为左上角,长度为 2 k 2^k 2k的正方形区域中的最大值. m n ( i , j , k ) mn(i,j,k) mn(i,j,k):以 ( i , j ) (i,j) (i,j)为左上角,长度为 2 k 2^k 2k正方形区域的最小值. m x ( i , j , k ) = m a x ( m x ( i , j , k − 1 ) , m a x ( m x ( i , j + ( 1 < < k ) , k − 1 ) , m x ( i + ( 1 < < k ) , j , k − 1 ) , m x ( i + ( 1 < < k ) , j + ( 1 < < k ) , k − 1 ) mx(i,j,k) =max(mx(i,j,k-1),max(mx(i,j+(1