#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) 编辑 收藏 引用 所属分类:
数据结构