hdu 4107 Gangster線分樹

/*
  a b c：[a,b]        c，         P(    ),   2*c
         
 hdu3954   ，    ：http://blog.csdn.net/wsniyufang/article/details/6702560
      min_dis;
          P ，  lazy
*/
using namespace std;
const int N=200001;
int n,m,P;
struct Node
{
    int L,R;//      
    int level,exp;//    ,1   ，2     P    ，exp       （            ）
    int min_dis;//         P    (      P )
    int lazy;//                 
}tree[4*N];
inline void search_up(int t)//         
{
    int nl=2*t,nr=2*t+1;
    tree[t].min_dis=min(tree[nl].min_dis,tree[nr].min_dis);
   // tree[t].exp=max(tree[nl].exp,tree[nr].exp);
   // tree[t].level=max(tree[nl].level,tree[nr].level);
}
void create(int t,int L,int R)//  
{
    tree[t].L=L;
    tree[t].R=R;
    tree[t].lazy=0;
    tree[t].level=1;
    tree[t].exp=0;
    tree[t].min_dis=P;
    if(L==R)//    
    {
    return ;
    }
   // tree[t].min_dis<<30;
    int mid=(L+R)>>1;
    create(t<<1,L,mid);
    create((t<<1)+1,mid+1,R);
}
inline void down(int t)// t lazy       
{
    int nl=t<<1,nr=(t<<1)+1;
    if(tree[nl].L==tree[nl].R)//       exp
    tree[nl].exp+=tree[nl].level*tree[t].lazy;
    
    tree[nl].lazy+=tree[t].lazy;
    tree[nl].min_dis-=tree[t].lazy;
    if(tree[nr].L==tree[nr].R)
    tree[nr].exp+=tree[nr].level*tree[t].lazy;
    
    tree[nr].lazy+=tree[t].lazy;
    tree[nr].min_dis-=tree[t].lazy;
    tree[t].lazy=0;
}
void update(int t,int L,int R,int val)
{
    int mid=(tree[t].R+tree[t].L)>>1,nl=t<<1,nr=(t<<1)+1;
    if(tree[t].L==tree[t].R)//       ，     、   min_dis
    {
        tree[t].exp+=tree[t].level*val;
        if(tree[t].exp>=P)
        {
        tree[t].level=2;
        tree[t].min_dis=1<<30;
        }
        else
        {
            tree[t].min_dis=P-tree[t].exp;
        }
        return ;
    }
    if(tree[t].L==L&&tree[t].R==R)
    {
        if(val>=tree[t].min_dis)//        ，     lazy
        {
            down(t);
            update(nl,tree[nl].L,tree[nl].R,val);//       ，         P       
            update(nr,tree[nr].L,tree[nr].R,val);
            search_up(t);//    t   
        }
        else //          
        {
            tree[t].min_dis-=val;
            tree[t].lazy+=val;
        }
        return ;
    }

    if(tree[t].lazy)//      
    {
        down(t);
    }
    if(R<=mid)  update(nl,L,R,val);
    else if(L>mid) update(nr,L,R,val);
    else {  update(nl,L,mid,val);update(nr,mid+1,R,val);}
    search_up(t);//  update   search_up，  t       ，t dis_min      
}

int ans[N];
void query(int t,int L,int R)
{
    int nl=t<<1,nr=(t<<1)+1;
    int mid=(tree[t].R+tree[t].L)>>1,tmp;
    if(tree[t].L==L&&tree[t].R==R&&L==R)
    {
        ans[L]=tree[t].exp;
        return ;
    }

        if(tree[t].lazy)//      
        {
            down(t);
        }

    if(R<=mid)query(nl,L,R);
    else if(L>mid)query(nr,L,R);
    else {query(nl,L,mid),query(nr,mid+1,R);}
    return ;
}
//    
inline int nextInt() {
    char c;
    while (c = getchar(), c < '0' || c > '9');
    int r = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') r = r * 10 + c - '0';
    return r;
}
int main()
{
    int L,R,Case,de,ti,temp;
    char op[3];
    while(scanf("%d%d%d",&n,&de,&P)!=EOF)
    {
        create(1,1,n);
        while(de--)
        {
            L=nextInt(); R=nextInt();
            temp=nextInt();
            update(1,L,R,temp);
        }
        query(1,1,n);
        for(int i=1;i<n;i++)
        printf("%d ",ans[i]);
        printf("%d
",ans[n]);
    }
}