#include  < iostream >
#include 
< algorithm >
#include 
< cstdio >
#include 
< cstdlib >
#include 
< cstring >

using   namespace  std;

#define  N 40001
#define  max(a,b) ( (a)>(b)?(a):(b) )

int  n,d[N << 1 ], idx[N << 1 ], pos, f[N << 1 ];

struct  Node{
    
int  x, y, ht;
    Node( 
int  a =   0 int  b =   0 int  c =   0  ):x(a), y(b), ht(c) {}
};

bool   operator < ( Node  const &  a, Node  const & b ){
    
return  a.ht <  b.ht; }
Node xyh[N];

int  bsearch(  int  v ){
    
int  left =   0 , right =  n *   2 ;
    
while ( left +   1 <  right ){
        
int  m =  (left + right) >> 1 ;
        
if ( d[m] >  v ) right =  m;
        
else   if ( d[m] <  v ) left =  m;
        
else   return  idx[m];
    }
    
return  idx[left]; }

int  tb[N * 8 ] =  { 0 };

void  insert(  int  l,  int  r,  int  a,  int  b,  int  rt,  int  h ){
    
if ( l ==  a  &&  r ==  b ){
        tb[rt]
=  max( tb[rt], h );  return ; }
    
if ( tb[rt] !=   0  ){
        tb[rt
<< 1 ] =  tb[rt];
        tb[(rt
<< 1 ) + 1 ] =  tb[rt];
        tb[rt]
=   0 ; }
    
int  m =  (l +  r) >> 1 ;
    
if ( b <=  m ) insert( l, m, a, b, rt <<   1 , h );
    
else   if ( a >=  m ) insert( m, r, a, b, (rt << 1 ) +   1 , h );
    
else {
        insert( l, m, a, m, rt
<<   1 , h );
        insert( m, r, m, b, (rt
<< 1 ) +   1 , h ); }
}

typedef __int64 INT;

INT ans;
void  sum(  int  l,  int  r,  int  rt ){
    
if ( tb[rt] >   0  ){
        ans
=  ans +  (INT)( f[r] -  f[l] ) *  (INT)tb[rt];
        
return ; }
    
if ( r >  l +   1  ){
        
int  m =  (l +  r) >>   1 ;
        sum( l, m, rt
<<   1  );
        sum( m, r, (rt
<< 1 ) +   1  );
    }        
}

inline 
int  read(){
    
char  ch;
    
int  d;
    
while ( (ch =  getchar()), ch <   ' 0 '   ||  ch >   ' 9 '  );
    d
=  ch -   ' 0 ' ;
    
while ( (ch =  getchar()), ch >=   ' 0 '   &&  ch <=   ' 9 '  ) d =  d *   10 +  ch -   ' 0 ' ;
    
return  d; }
    
int  main(){
    
int  a, b, h;
    scanf(
" %d " , & n);
    
for int  i =   0 ; i <  n;  ++ i ){
        a
=  read(), b =  read(), h =  read();
        xyh[i]
=  Node( a, b, h );
        d[i
<< 1 ] =  a, d[(i << 1 ) + 1 ] =  b; }
    sort( d, d
+  n *   2  );
    pos
=   1 ; idx[ 0 ] =   1 ; f[ 1 ] =  d[ 0 ];
    
for int  i =   1 ; i <  n *   2 ++ i ){
        
if ( d[i] !=  d[i - 1 ] ) idx[i] =   ++ pos;
        
else  idx[i] =  idx[i - 1 ];
        f[ idx[i] ]
=  d[i];
    }
    sort( xyh, xyh
+  n );
    
for int  i =   0 ; i <  n;  ++ i ){
        a
=  bsearch( xyh[i].x ), b =  bsearch( xyh[i].y );
        insert( 
1 , pos, a, b,  1 , xyh[i].ht );
    }        
    ans
=   0
    sum( 
1 , pos,  1  );
    printf(
" %I64d\n " , ans );
    
    
return   0 ;
}

posted on 2009-07-15 12:39 Darren 阅读(402) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理