Segment Tree Problem:Poj 3277

Правка en1, от _kryptonyte_, 2015-06-09 15:36:38

Problem Link : http://poj.org/problem?id=3277 The full code, http://ideone.com/RF1JfE

This is a very straight forward segment tree problem( if I don't miss anything ) , but unfortunately it just don't get AC. Obviously I miss something. Can anybody help. I try to build a seg tree with minimum 2 range sized leaf nodes by following code where Tree[nd] holds the height of the range.

void build( int nd , int st , int en ) {
    Tree[nd] = 0 ;
    if( st+1 == en )return ;
    build( (nd<<1) , st , (st+en)>>1 );
    build( (nd<<1)+1 , (st+en)>>1 , en );
} 

Then I update like following manner, here l,r is the index of the value given in the problem,

void update( int nd , int st , int en ) {
    propagate(nd,st,en) ;
    if( st == en ) return  ;
    if( st > r || en < l ) return ;
    if( st>=l && en <= r ) {
        Tree[nd] = max( Tree[nd] , h ) ;
        return ;
    }
    if( st+1 == en ) return  ;
    update( (nd<<1) , st , (st+en)>>1 );
    update( (nd<<1)+1 , (st+en)>>1 , en );
}

And finally run the query,

long long query( int nd , int st , int en ) {
    propagate(nd,st,en) ;
    if( st == en ) return 0 ;
    if( en-st == 1 ) {
        long long ans = (V[en]-V[st])*Tree[nd] ;
        return ans ;
    }

    return query( (nd<<1) , st , (st+en)>>1 )
           +query( (nd<<1)+1 , (st+en)>>1 , en );
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский _kryptonyte_ 2015-06-09 15:36:38 1445 Initial revision (published)