#include
#include
#include
#include
using namespace std;
//NOJ 1044 类矩形并面积 线段树
/*
4
1 4 3
2 7 2
6 9 4
9 10 3
6
1 5 10
3 8 8
4 7 20
8 9 40
10 14 30
12 13 15
输出
28
258
*/
#define NMAX 65000
typedef struct dis
{ //这里的ll和rr已经被离散了
__int64 ll;
__int64 rr;
__int64 count;
__int64 len;//测度
}dis;
typedef struct helloh
{
__int64 high;//竖线的高度
__int64 x;//竖线所在的水平位置
bool add;//竖线是矩形的左边(true)，还是右边(false)
}helloh;
__int64 tth[NMAX*2];//已就high做升序排序，有重复的high
__int64 clh[NMAX*2];//剔除tth中有重复的high所得
helloh temph[NMAX*2];//已就x做升序排序
helloh srh[NMAX*2];//未经处理
dis hh[NMAX*4];//high的线段树结点
bool cmpx(struct helloh a,struct helloh b) {return a.x bool cmph(__int64 a,__int64 b) {return a
__int64 findh(__int64 number,__int64 num)
{ //根据实际高度high，查找离散高度high
int low,high,mid;
low=1;high=num;
mid=(low+high)/2;
while(low { //经典的二分法查找
if(clh[mid]==number) break;
else if(clh[mid] else high=mid-1;
mid=(low+high)/2;
}
return mid;
}
__int64 lisanh(__int64 num)
{
__int64 i,j;
for(i=1;i sort(temph+1,temph+1+num,cmpx);//temph按x升序排列
sort(tth+1,tth+1+num,cmph);//tth按high升序排列
clh[0]=0;
clh[1]=tth[1];
j=1;
for(i=2;i { //clh中的high无重复，且升序排列，用于构造线段树
if(tth[i-1] !=tth[i] ) clh[++j]=tth[i] ;
}
return j;
}
void create_tree(__int64 p,__int64 left,__int64 right)
{ //构造线段树
__int64 mid;
hh[p].ll=left;
hh[p].rr=right;
hh[p].count=0;
if(left+1 { //如果不是叶子结点，构造子结点
mid=(left+right)/2;
create_tree(2*p,left,mid);
create_tree(2*p+1,mid,right);
}
}
void update(int p)
{ //对测度进行维护
if(hh[p].count == 0)
{
if(hh[p].ll+1 == hh[p].rr) hh[p].len=0;
else hh[p].len=hh[2*p].len+hh[2*p+1].len;
}
else hh[p].len= clh[hh[p].rr]-clh[hh[p].ll];
}
void insert_tree(__int64 p,__int64 left,__int64 right)
{ //插入线段
__int64 mid;
//完全覆盖
if(hh[p].ll==left&&hh[p].rr==right) hh[p].count++;
else
{ //部分覆盖，往子节点插入线段
mid=(hh[p].ll+hh[p].rr)/2;
if(right else if(left>=mid) insert_tree(2*p+1,left,right);
else
{
insert_tree(2*p,left,mid);
insert_tree(2*p+1,mid,right);
}
}
update(p);
}
void delete_tree(__int64 p,__int64 left,__int64 right)
{ //删除线段
__int64 mid;
//完全覆盖
if(hh[p].ll==left&&hh[p].rr==right) hh[p].count--;
else
{ //部分覆盖，往子节点插入线段
mid=(hh[p].ll+hh[p].rr)/2;
if(right else if(left>=mid) delete_tree(2*p+1,left,right);
else
{
delete_tree(2*p,left,mid);
delete_tree(2*p+1,mid,right);
}
}
update(p);
}
__int64 get_count(__int64 p)
{ //得到根的测度
int mm;
if(hh[p].count>0)
{ //完全覆盖
mm=clh[hh[p].rr]-clh[hh[p].ll];
return mm;
}
else
{ //部分覆盖或不覆盖
if(hh[p].ll+1==hh[p].rr) return 0;//叶子结点情况
else
{ //内部结点情况
mm=get_count(2*p)+get_count(2*p+1);//递归地查找子节点
return mm;
}
}
}
__int64 init(__int64 num)
{ //对高度high进行离散处理，同时构造线段树
__int64 hnum;
hnum=lisanh(num);
create_tree(1,0,hnum);
return hnum;
}
__int64 solve(__int64 num,__int64 hnum)
{ //求面积
__int64 i;
__int64 sql=0;//面积
__int64 lastx=0;//上一次竖线的水平位置
__int64 lsh;//将实际高度转化后所得到的离散高度
for(i=1;i {
lsh=findh(temph[i].high ,hnum);//求离散高度
if(lastx!=0) sql+=hh[1].len * (temph[i].x-lastx); //get_count(1)*(temph[i].x-lastx);//求面积
// if(lastx!=0) sql+=get_count(1) * (temph[i].x-lastx);
if(temph[i].add==true) insert_tree(1,0,lsh);//如果是矩形的左边竖线，往线段树插入线段
else delete_tree(1,0,lsh);//否则，删除线段
lastx=temph[i].x;//这个。。。。显然
}
return sql;
}
int main()
{
__int64 num,ta,tb,th,i,j,hnum;
while(scanf("%I64d",&num)!=EOF)
{
j=0;
memset(tth,0,sizeof(tth));
memset(clh,0,sizeof(clh));
memset(temph,0,sizeof(temph));
memset(srh,0,sizeof(srh));
memset(hh,0,sizeof(hh));
for(i=1;i {
scanf("%I64d%I64d%I64d",&ta,&tb,&th);
srh[++j].add=true;
srh[j].high=th;
srh[j].x=ta;
srh[++j].add=false;
srh[j].high=th;
srh[j].x=tb;
}
hnum=init(2*num);
printf("%I64d\n",solve(2*num,hnum));
}
return 0;
}
