HDU 4107 Gangster

http://acm.hdu.edu.cn/showproblem.php?pid=4107
제목: 배열 을 지정 합 니 다. 초기 에 배열 의 값 은 모두 0 입 니 다. 배열 의 한 구간 에 값 을 추가 할 때마다 이 구간 의 원래 값 이 P 를 초과 하면 이 수 는 2 * val 을 증가 합 니 다. 그렇지 않 으 면 val 을 증가 합 니 다.몇 번 의 부가 가치 이후 배열 의 최종 요소 의 가 치 를 구하 다.
알고리즘: 선분 트 리 + lazy 최적화
코드:

/*
HDU 4107 Gangster
Tips : segment Tree + lazy
runtime : 810ms     
*/
#include<stdio.h>
#include<string.h>
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)
#define MID(a,b) ( (a+b)>>1 )
#define MAX 200001
#define MIN(a,b) (a>b?b:a)
struct Node{
    int L,R ;           //       
    int rank , exp ;    //        rank         ，exp            
    int min_dis ;       //     ，       p          
    int lazy ;          //    ，                 ，  lazy  
}NN[4*MAX] ;
int n,m,p;
int ans[MAX] ;
//  
void Build(int t,int l,int r){          
    int nl = LL(t) , nr = RR(t) ;
    NN[t].L = l ; NN[t].R = r ;
    NN[t].rank = 1 ; NN[t].exp = 0 ;
    NN[t].min_dis = p ;
    NN[t].lazy = 0 ;
    if(l == r) return ;
    int mid = MID(l,r);
    Build(nl,l,mid) ;
    Build(nr,mid+1,r) ;
}
//         dis_min  
inline void search(int t){
    int nl = LL(t) , nr = RR(t) ;
    NN[t].min_dis = MIN(NN[nl].min_dis , NN[nr].min_dis) ;
}
//      lazy           
inline void down(int t){
    int nl=LL(t) , nr = RR(t) ;
    if(NN[nl].L == NN[nl].R){
        NN[nl].exp += NN[nl].rank * NN[t].lazy ;
    }
    NN[nl].lazy += NN[t].lazy ;
    NN[nl].min_dis -= NN[t].lazy ;
    if(NN[nr].L == NN[nr].R){
        NN[nr].exp += NN[nr].rank * NN[t].lazy ;
    }
    NN[nr].lazy += NN[t].lazy ;
    NN[nr].min_dis -= NN[t].lazy ;

    NN[t].lazy = 0 ;
}
//      ,   [l,r]       val  
inline void update(int t,int l,int r,int val){
    int mid = MID(NN[t].L,NN[t].R) ;
    int nl = LL(t) , nr = RR(t) ;
    if( NN[t].L == NN[t].R ){               //       
        NN[t].exp += NN[t].rank * val ;         //       exp ，         
        if(NN[t].exp >= p){         //        
            NN[t].rank = 2 ;
            NN[t].min_dis = (1<<30) ;
        }
        else{                       //     
            NN[t].min_dis = p-NN[t].exp ;
        }
        return ;
    }
    if(NN[t].L==l && NN[t].R==r){           //         
        if(NN[t].min_dis <= val){           //             ，      lazy，    lazy  
            down(t);                //     lazy
            update(nl,NN[nl].L,NN[nl].R,val) ;
            update(nr,NN[nr].L,NN[nr].R,val) ;
            search(t);              //      dis_min
        }
        else{                       //    lazy  
            NN[t].lazy += val ;
            NN[t].min_dis -= val ;
        }
        return ;
    }
    if(NN[t].lazy)              //         ，        ，   lazy  
        down(t) ;
    if(r<=mid)  update(nl,l,r,val);
    else if(l>=mid+1)   update(nr,l,r,val) ;
    else{
        update(nl,l,mid,val);
        update(nr,mid+1,r,val) ;
    }
    search(t) ;
    return ;
}
//          
void query(int t,int l,int r){
    int nl = LL(t) , nr = RR(t) ;
    if(NN[t].L == NN[t].R) {
        ans[l] = NN[t].exp ;
        return ;
    }
    if(NN[t].lazy)  down(t) ;
    int mid = MID(NN[t].L,NN[t].R) ;
    query(nl,l,mid) ;
    query(nr,mid+1,r) ;
}
//    
inline void scan(int &n){
    char cc ;
    while(cc=getchar() , cc<'0'|| cc>'9') ;
    n = cc - '0' ;
    while(cc=getchar() , cc>='0' && cc<='9')
        n = n * 10 + cc - '0' ;
}
int main(){
    int L,R,val ;
    while(scanf("%d %d %d",&n,&m,&p)!=EOF){
        Build(1,1,n);
        for(int i=1;i<=m;i++){
            scan(L) ; scan(R); scan(val);
            update(1,L,R,val) ;
        }
        query(1,1,n) ;
        for(int i=1;i<=n;i++){
            if(i!=1)    printf(" ");
            printf("%d",ans[i]);
        }
        printf("
");
    }
    return 0 ;
}