hdu4107 线段树水题

这道题确定够坑的 太卡时间了 我只想说G++超时 C++刚刚过

每个节点记录最大伤害 最小伤害 子节点应该增加的伤害 注意更新时停止的条件

#include
  
   
#include
   
     #include
     
     using namespace std
     ; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) 
      struct node
      { int large
     ,few
     ,add
     ; }num
     [4
     *200000
     ]; int k
     ,flash
     ; int max
     (int a
     ,int b
     ) { return a
     >b
     ?a
     :b
     ; } int min
     (int a
     ,int b
     ) { return a
     <b
     ?a
     :b
     ; } int make
     (int L
     ,int R
     ,int mark
     ) { int mid
     =(L
     +R
     )/2
     ; num
     [mark
     ].large
     =num
     [mark
     ].few
     =num
     [mark
     ].add
     =0
     ; if(L
     ==R
     ) return 0
     ; make
     (L
     ,mid
     ,LL
     (mark
     )); make
     (mid
     +1
     ,R
     ,RR
     (mark
     )); return 0
     ; } int deal
     (int a
     ) { num
     [LL
     (a
     )].few
     +=num
     [a
     ].add
     ; num
     [LL
     (a
     )].large
     +=num
     [a
     ].add
     ; num
     [RR
     (a
     )].large
     +=num
     [a
     ].add
     ; num
     [RR
     (a
     )].few
     +=num
     [a
     ].add
     ; num
     [LL
     (a
     )].add
     +=num
     [a
     ].add
     ; num
     [RR
     (a
     )].add
     +=num
     [a
     ].add
     ; num
     [a
     ].add
     =0
     ; return 0
     ; } int update
     (int L
     ,int R
     ,int left
     ,int right
     ,int mark
     ,int x
     ) { int mid
     =(L
     +R
     )/2
     ; if(L
     ==left
     &&R
     ==right
     ) { if(num
     [mark
     ].few
     >=k
     ) { num
     [mark
     ].few
     +=2
     *x
     ; num
     [mark
     ].large
     +=2
     *x
     ; num
     [mark
     ].add
     +=2
     *x
     ; return 0
     ; } else if(num
     [mark
     ].large
     <k
     ) { num
     [mark
     ].few
     +=x
     ; num
     [mark
     ].large
     +=x
     ; num
     [mark
     ].add
     +=x
     ; return 0
     ; } deal
     (mark
     ); update
     (L
     ,mid
     ,L
     ,mid
     ,LL
     (mark
     ),x
     ); update
     (mid
     +1
     ,R
     ,mid
     +1
     ,R
     ,RR
     (mark
     ),x
     ); num
     [mark
     ].large
     =max
     (num
     [LL
     (mark
     )].large
     ,num
     [RR
     (mark
     )].large
     ); num
     [mark
     ].few
     =min
     (num
     [LL
     (mark
     )].few
     ,num
     [RR
     (mark
     )].few
     ); return 0
     ; } if(num
     [mark
     ].add
     >0
     ) { deal
     (mark
     ); } if(right
     <=mid
     ) { update
     (L
     ,mid
     ,left
     ,right
     ,LL
     (mark
     ),x
     ); } else if(left
     >mid
     ) { update
     (mid
     +1
     ,R
     ,left
     ,right
     ,RR
     (mark
     ),x
     ); } else { update
     (L
     ,mid
     ,left
     ,mid
     ,LL
     (mark
     ),x
     ); update
     (mid
     +1
     ,R
     ,mid
     +1
     ,right
     ,RR
     (mark
     ),x
     ); } num
     [mark
     ].large
     =max
     (num
     [LL
     (mark
     )].large
     ,num
     [RR
     (mark
     )].large
     ); num
     [mark
     ].few
     =min
     (num
     [LL
     (mark
     )].few
     ,num
     [RR
     (mark
     )].few
     ); return 0
     ; } int print
     (int L
     ,int R
     ,int mark
     ) { int mid
     =(L
     +R
     )/2
     ; if(L
     ==R
     ) { if(flash
     !=0
     ) printf
     (" "
     ); flash
     ++; printf
     ("%d"
     ,num
     [mark
     ].large
     ); return 0
     ; } if(num
     [mark
     ].add
     >0
     ) { deal
     (mark
     ); } print
     (L
     ,mid
     ,LL
     (mark
     )); print
     (mid
     +1
     ,R
     ,RR
     (mark
     )); return 0
     ; } int main() { int i
     ,j
     ,n
     ,m
     ,a
     ,b
     ,c
     ; while(~scanf
     ("%d%d%d"
     ,&n
     ,&m
     ,&k
     )) { //memset(num,0,sizeof(num)); make
     (1
     ,n
     ,1
     ); for(i
     =1
     ;i
     <=m
     ;i
     ++) { scanf
     ("%d%d%d"
     ,&a
     ,&b
     ,&c
     ); update
     (1
     ,n
     ,a
     ,b
     ,1
     ,c
     ); } flash
     =0
     ; print
     (1
     ,n
     ,1
     ); printf
     ("\n"
     ); } return 0
     ; }