BZOJ-2006: [NOI2010]超级钢琴

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2006

刚开始搞错了题意，以为每个和弦里的美妙度集合要不同。。。傻了半天终于理解了，1Y

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
 
using namespace std ;
 
#define MAXN 500100
#define MAXD 24
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define ll long long
 
int a[ MAXN ] , n , k , pre[ MAXN ] , st[ MAXN ][ MAXD ] , D , L , R ;
int pos[ MAXN ][ MAXD ] ;
 
int Min( int l , int r ) {
    int d = int( log2( r - l + 1 ) ) ;
    return min( st[ l ][ d ] , st[ r - ( 1 << d ) + 1 ][ d ] ) ;
}
 
int Pos( int l , int r ) {
    int d = int( log2( r - l + 1 ) ) ;
    if ( st[ l ][ d ] < st[ r - ( 1 << d ) + 1 ][ d ] ) {
        return pos[ l ][ d ] ; 
    } else return pos[ r - ( 1 << d ) + 1 ][ d ] ;
}
 
struct node {
    int l , r , x ;
    ll v ;
    node( int _l , int _r , int _x ) : l( _l ) , r( _r ) , x( _x ) , v( pre[ _x ] - Min( _l , _r ) ) {
         
    }
    bool operator < ( const node &a ) const {
        return v < a.v ;
    }
};
priority_queue < node > q ;
 
void Init(  ) {
    scanf( "%d%d%d%d" , &n , &k , &L , &R ) ;
    rep( i , n ) scanf( "%d" , &a[ i ] ) ;
    pre[ 0 ] = 0 ;
    rep( i , n ) pre[ i ] = pre[ i - 1 ] + a[ i ] ;
    D = int( log2( n ) ) + 1 ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        st[ i ][ 0 ] = pre[ i ] , pos[ i ][ 0 ] = i ;
    }
    rep( i , D ) {
        for ( int j = 0 ; j <= n ; ++ j ) {
            if ( st[ j ][ i - 1 ] < st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ) {
                st[ j ][ i ] = st[ j ][ i - 1 ] , pos[ j ][ i ] = pos[ j ][ i - 1 ] ;
            } else {
                st[ j ][ i ] = st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ;
                pos[ j ][ i ] = pos[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ;
            }
        }
    }
    while ( ! q.empty(  ) ) q.pop(  ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        int l = max( 0 , i - R ) , r = i - L ;
        if ( r < 0 ) continue ;
        q.push( node( l , r , i ) ) ;
    }
}
 
void Solve(  ) {
    ll ans = 0 ;
    while ( k -- ) {
        node ret = q.top(  ) ; q.pop(  ) ;
        ans += ret.v ;
        int p = Pos( ret.l , ret.r ) ;
        if ( ret.l < p ) q.push( node( ret.l , p - 1 , ret.x ) ) ;
        if ( ret.r > p ) q.push( node( p + 1 , ret.r , ret.x ) ) ;
    }
    printf( "%lld\n" , ans ) ;
}
 
int main(  ) {
    Init(  ) ;
    Solve(  ) ;
    return 0 ;
}