#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 閱讀(410)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構