题目链接：
codeforces 487B
题目大意：
给出一个序列，要把序列划分成段，每一段最少有L个元素，段中的最大元素和最小元素之差不大于s，问划分的段的最少的数量是多少。
题目分析：首先用rmq维护区间最大值和区间最小值。然后按顺序扫描数组，线段树维护的数组，每个记录当前点作为最后一个点的前i个点划分的最小的段数，那么每次更新就是二分找到可以转移到我的最远距离，，然后再选取与我距离大于l的那部分，取最小值即可。最终结果就是线段树维护的数组的最后一个位置的元素的值。 AC代码：;int n,s,l,a[MAX];int dp[MAX][30];int dp2[MAX][30];void make ( ){for ( int i = 1 ; i <= n ; i++ )dp[i][0] = a[i],dp2[i][0] = a[i];for ( int j = 1 ; (1<<j) <= n ; j++ )for ( int i = 1 ; i + (1<<j) -1 <= n ; i++ ){dp[i][j] = max ( dp[i][j-1] , dp[i+(1<<(j-1))][j-1] );dp2[i][j] = min ( dp2[i][j-1] , dp2[i+(1<<(j-1))][j-1] );} }int big ( int l , int r ){int k = (int)((log(r-l+1)*1.0)/(log(2.0)));return max ( dp[l][k] , dp[r-(1<<k)+1][k] );}int small ( int l , int r ){int k = (int)((log(r-l+1)*1.0)/(log(2.0)));return min ( dp2[l][k] , dp2[r-(1<<k)+1][k] );}struct Tree{int minn,l,r;}tree[MAX<<2];void build ( int u , int l, int r ){tree[u].l = l;tree[u].r = r;tree[u].minn = 1<<30;if ( l == r ) return;int mid = (l+r)>>1;build ( u<<1 , l , mid );build ( u<<1|1 , mid+1 , r );}void push_up ( int u ){tree[u].minn = min ( tree[u<<1].minn , tree[u<<1|1].minn );}void update ( int u , int x , int v ){int l = tree[u].l;int r = tree[u].r;if ( l == r){tree[u].minn = v;return;}int mid = l+r>>1;if ( x > mid )update ( u<<1|1 , x , v );elseupdate ( u<<1 , x , v );push_up (u );}int query ( int u , int left , int right ){int l = tree[u].l;int r = tree[u].r;if ( left <= l && r <= right )return tree[u].minn;int ret = 1<<30;int mid = l+r>>1;if ( left <= mid && right >= l )ret = min ( ret , query ( u<<1 , left , right ) );if ( left <= r && right > mid )ret = min ( ret , query ( u<<1|1 , left , right ) );return ret;}int bsearch ( int x ){int l = 1, r = x , mid;while ( l < r ){mid = (l+r)>>1;if ( big ( mid , x ) – small( mid , x ) > s ) l = mid+1;else r = mid;}return l;}int main () {while ( ~scanf ( “%d%d%d” , &n , &s , &l ) ){for ( int i = 1 ; i <= n ; i ++ )scanf ( “%d” , &a[i] );make ( );build ( 1 , 1 , n );for ( int i = 1 ; i <= n ; i++ ){int ll = bsearch ( i )-1;int rr = i-l;if ( rr < ll ) continue;if ( ll <= 0 ){update ( 1 , i , 1 );continue;}int x = query ( 1 , ll , rr );update ( 1 , i , x+1 );}int x = query ( 1 , n , n );if ( x == 1<<30 )puts (“-1” );elseprintf ( “%d\n” , x );return 0;}}
友谊之花、爱情之树、以及遗憾之泪！
