USTC_1558 Charritable Exchange弦断樹最適化dp

http://acm.uestc.edu.cn/problem.php?pid=1558
件名:
Nの中で交換するタイプがあって、それぞれの交換はすべて(a、b、c)の表示の意味はa元のものを使うので、cの時間を使ってそれをbのものになることができて、データはa<=bを保証して、初期の時あなたは1元のものがあって、最後の価値を最も最低のMにならせて、使うべきな最小の時間はいくらですか?
この問題はデータ量が小さいなら、最短で作ることが考えられます.最短で作るとO(N^2)の複雑さが必要ですので、これは無理です.私たちはdpで求めようと考えています.まず、すべての価値を離散化して、2＊N個の点に変えました.そして、私達が得られる価値はきっとある取引のbにあります.そうすると、私達はdp[i]でi元の最小消費時間(ここのiは離散化後のi)を表します.このようにdpの移動方程式はdp[i]=min(dp[k])+exchange(exj)に等しくなります.そして、exchange(j).a<=k==exchange(j).bは、決定点kを探すたびに、(a,b)の中でdpの最小値を見つけます.そうすると、O(logn)の時間内に線分樹で最小値を見つけられます.また、将来性を維持するために、exchangeごとにbのサイズに並べ替えられます.これで順番にdpができます. 
コード:

#include<stdio.h>
#include<string.h>
#include<algorithm>

typedef long long LL ;
const int MAXN = 100010 ;
int N , M ;
LL T[MAXN<<1] ;
const LL INF = 1e16  ;

struct Point{
    int s, e,t ;
    Point(){}
    Point(int a, int b ,int c)
    :s(a) , e(b) , t(c) {}
    bool operator<( const Point& cmp ) const {
        return e < cmp.e ;
    }
}p[MAXN] ;

LL min[MAXN<<3] ;
int cnt ;

inline LL MIN(LL a, LL b){
    return a > b ? b : a ;
}

void update(int l ,int r, int idx, int pos, LL val ){
    if(l == r){
        min[idx] = MIN( min[idx] , val );
        return ;
    }
    int mid = (l + r) >> 1 ;
    int ls = idx<<1 , rs = idx<<1|1 ;
    if( pos<=mid )  update(l , mid ,ls , pos , val );
    else            update(mid+1, r, rs , pos, val );
    min[idx] = MIN( min[ls] , min[rs] );
}

int find(int v, int l ,int r){
    while( l<r ){
        int mid = (l + r) >> 1 ;
        if( T[mid] < v )    l = mid + 1 ;
        else    r = mid ;
    }
    return l ;
}

LL query(int l, int r, int idx, int a, int b){
    if(l==a && r==b){
        return min[idx] ;
    }
    int mid = (l + r) >> 1 ;
    int ls = idx<<1 ,rs = idx<<1|1 ;
    if( b<=mid )    return query(l , mid , ls , a, b) ;
    else if( mid<a )    return query(mid+1, r, rs, a ,b );
    else{
        return MIN( query(l ,mid, ls , a ,mid )  , query(mid+1, r ,rs , mid+1, b) );
    }
}

void build(int l , int r, int idx){
    min[idx] = INF ;
    if(l == r) {
        return ;
    }
    int mid = (l + r) >> 1 ;
    int ls = idx<<1 , rs = idx<<1|1 ;
    build(l , mid ,ls ) ;
    build(mid+1, r, rs) ;
}

void solve(int n){
    build(0,  n ,1 );
    update(0 , n ,1 ,0 , 0);
    for(int i=0;i<N;i++){
        int s = p[i].s  ;
        int e = p[i].e ;
        LL tt = p[i].t ;
        LL _min = query(0 , n ,1 , s , e );
        if( _min == INF )   continue ;
        update(0 , n ,1 , e , _min+tt ) ;
    }
    int  pos = find(M , 0 , n );
    LL ans = query(0 , n , 1 ,pos, n ) ;
    if( ans == INF )    printf("-1
");
    else    printf("%lld
",ans);
}

int main(){
    int TT , a, b, c ;
    scanf("%d",&TT);
    for(int cas=1;cas<=TT;cas++){
        scanf("%d %d",&N,&M);
        cnt = 0 ;
        for(int i=0;i<N;i++){
            scanf("%d %d %d",&a,&b,&c);
            p[i] = Point(b ,a ,c );
            T[cnt++] = b ; T[cnt++] = a ;
        }
        T[cnt++] = M ;
        T[cnt++] = 1 ;      //   NC      ，WA N 。。。
        std::sort(T, T+cnt ) ;
        int n = 0 ;
        for(int i=1;i<cnt;i++){
            if( T[i]!=T[i-1] )  T[++n] = T[i] ;
        }
        for(int i=0;i<N;i++){
            p[i].s = find( p[i].s , 0 , n ) ;
            p[i].e = find( p[i].e , 0 , n ) ;
        }
        std::sort(p ,p + N) ;
        printf("Case #%d: ",cas);
        solve(n);
    }
    return 0;
}