最小白的RMQ，求第i到第j的最大值和最小值差值。采用SparseTable算法，其实就是一种相当高效的打表，空间范围nlogn，每次查询的时间只需要常数。 假如是一般的打表，对每组i和j，记录下第i到第j的最大值和最小值，需要的空间为N2，N增大时显然无法满足要求。因此考虑改进算法，适当扩大时间，缩小空间，使之平衡。 ST采用的方法相当高效，二分划分，把每个i的所辖范围划分成1，2，4，8，16的小块，和操作系统中伙伴系统的划分倒有几分类似。 以最大值为例。F(i,j)表示以i位元素开始，连续2i个元素中的最大值。初值设所有的F(i,0)即为i的值。 那么，F[i,j]=max（F[i，j-1],F[i+2^(j-1)，j-1]）。这个等式不难推出。 然后计算l和r区间最大值时，只要划分成两块小且互相覆盖的区间就可以了。 第一次做的时候计算最后区间出了点差错，百思不得其解。为什么是(ln(r-l+1)/ln(2))；r-l计算莫非会出精度错误？ #include <cstdio>#include <cmath>#include <string> int N, Q, a[50000], s[16][50000], t[16][50000], A, B, L; #define max( x, y ) ( (x) > (y) ? (x) : (y) )#define min( x, y ) ( (x) < (y) ? (x) : (y) ) void pt (){ int i, j; for ( i = 0; i <= L; i ++ ) { for ( j = 0; j < N; j ++ ) { printf ( "%d ", t[i][j] ); } printf ( "\n" ); }} void init (){ memset ( s, 0, sizeof ( s ) ); memset ( t, 0, sizeof ( t ) ); scanf ( "%d %d", &N, &Q ); int i, j; L = log ( double ( N ) ) / log ( 2.0 ); printf ( "%d\n", L ); for ( i = 0; i < N; i ++ ) { scanf ( "%d", &a[i] ); } for ( j = 0; j < N; j ++ ) { s[0][j] = t[0][j] = a[j]; } for ( i = 1; i <= L; i ++ ) { for ( j = 0; j < N; j ++ ) { int j1 = j + ( 1 << ( i - 1 ) ); if ( j1 < N ) { s[i][j] = min ( s[i - 1][j], s[i - 1][j1] ); t[i][j] = max ( t[i - 1][j], t[i - 1][j1] ); } else { s[i][j] = s[i - 1][j]; t[i][j] = t[i - 1][j]; } } } //pt ();} int rmq ( int l, int r ){ int m = ( log ( double ( r - l + 1 ) ) / log ( 2.0 ) ); int l0 = l, r0 = r - ( 1 << m ) + 1; //printf ( "%d %d %d\n", m, l0, r0 ); int mx = max ( t[m][l0], t[m][r0] ); int mn = min ( s[m][l0], s[m][r0] ); return mx - mn;} void calc (){ int i; for ( i = 0; i < Q; i ++ ) { scanf ( "%d %d", &A, &B ); A --, B --; if ( A == B ) { printf ( "0\n" ); continue; } printf ( "%d\n", rmq ( A, B ) ); }} int main (){ //freopen ( "t.txt", "r", stdin ); init (); calc (); return 0;}
评论