[선분 수] HDU 1698

한 걸음 한 걸음 라인 트 리 이해 하기: http://www.cnblogs.com/TenosDoIt/p/3453089.html#f
아니면 이 주소 입 니까? 이번 에는 최적화 에 사용 되 는 구간 지연 업 데 이 트 를 사 용 했 습 니 다. 시간 복잡 도 는 O (lgn) 입 니 다.
PS: 변 수 를 제대로 명명 하지 않 은 구덩이 아버지 에 게......................................................

#include 
#include 
#include 

#define lson root * 2
#define rson root * 2 + 1

using namespace std;
const int X = 100002 << 2;

int Tree[ X ];
int flag[ X ]; //    

void build ( int root, int ST, int END ) {
        if ( ST == END ) {
                Tree[ root ] = 1;
                flag[ root ] = 0;
        } else {
                int mid = ( ST + END ) / 2;
                build ( lson, ST, mid );
                build ( rson, mid + 1, END );
                Tree[ root ] = Tree[ lson ] + Tree[ rson ];
        }
}

//        O(lgn)
//   root       
void pushDown ( int root, int st, int end ) {
        if ( flag[ root ] ) {
                flag[ lson ] = flag[ rson ] = flag[ root ]; //  z（    ）      
                int mid = ( st + end ) / 2;
                Tree[ lson ] =
                    ( mid - st + 1 ) * flag[ root ]; //                 * z
                Tree[ rson ] = ( end - ( mid + 1 ) + 1 ) * flag[ root ];
                flag[ root ] = 0;
        }
}

// ST END --> required
// st,end --> now
void update ( int root, int st, int end, int ST, int END, int val ) {
        if ( st > END || end < ST )
                return;

        //          
        if ( st >= ST && end <= END ) {
                flag[ root ] = val;
                Tree[ root ] = val * ( end - st + 1 ); //           
                return;
        }

        //  flag，       
        pushDown ( root, st, end );

        int mid = ( st + end ) / 2;
        if ( mid >= ST )
                update ( lson, st, mid, ST, END, val );
        if ( mid < END )
                update ( rson, mid + 1, end, ST, END, val );

        Tree[ root ] = Tree[ lson ] + Tree[ rson ];
}

int main () {
        int n;
        scanf ( "%d", &n );
        for ( int i = 1; i <= n; ++i ) {

                memset ( flag, 0, sizeof ( flag ) );

                int N, Q;
                scanf ( "%d%d", &N, &Q );

                build ( 1, 1, N );

                while ( Q-- ) {
                        int x, y, z;
                        scanf ( "%d%d%d", &x, &y, &z );
                        update ( 1, 1, N, x, y, z );
                }

                printf ( "Case %d: The total value of the hook is %d.
", i, Tree[ 1 ] );
        }

        return 0;
}