```
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node
{
int l,r,lc,rc,c,d;
}tr[410000];int len=0,s1[210000],s2[210000],n;
ll suma[210000],sum[210000],sumh[210000],ans=0;
struct LSnode
{
int p,z;ll x;
}A[210000],H[210000];
bool cmp(LSnode x,LSnode y){return x.x<y.x;}
inline int mymax(int x,int y){return x>y?x:y;}
void build(int l,int r)
{
len++;int now=len;
tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;
tr[now].c=-1;tr[now].d=0;
if(l<r)
{
int mid=(l+r)/2;
tr[now].lc=len+1;build(l,mid);
tr[now].rc=len+1;build(mid+1,r);
}
}
void change(int now,int l,int r,int k)
{
if(tr[now].l==l && tr[now].r==r && tr[now].c<k){tr[now].c=k;tr[now].d=k;return ;}
int mid=(tr[now].l+tr[now].r)/2;
int lc=tr[now].lc,rc=tr[now].rc;
if(tr[now].d>0)
{
tr[rc].c=tr[lc].c=tr[now].c;
tr[rc].d=tr[lc].d=tr[now].d;
}
if(r<=mid)change(lc,l,r,k);
else if(mid+1<=l)change(rc,l,r,k);
else change(lc,l,mid,k),change(rc,mid+1,r,k);
tr[now].c=mymax(tr[lc].c,tr[rc].c);
if(tr[lc].d==tr[rc].d && tr[lc].d>0)tr[now].d=tr[lc].d;
else tr[now].d=-1;
}
int ansl,ansr,aans=-1;
void find(int now,int l,int r)
{
if(tr[now].d>0 && aans<0){aans=tr[now].d,ansl=tr[now].l;return ;}
if(tr[now].d!=aans && aans>0)
{
ansr=tr[now].l-1;
if(suma[ansr+1]>0)ansr++,ans+=ll((suma[ansr]-suma[ansl])*aans);
else ans+=ll((suma[ansr]-suma[ansl]+1)*aans);
if(tr[now].d>0){ansl=tr[now].l;aans=tr[now].d;return ;}
else aans=-1;
}
if(l==r)return ;
int mid=(tr[now].l+tr[now].r)/2;
int lc=tr[now].lc,rc=tr[now].rc;
find(lc,l,mid);find(rc,mid+1,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&A[i*2-1].x,&A[i*2].x,&H[i].x);
A[i*2-1].x++;
A[i*2-1].p=i*2-1;A[i*2].p=i*2;H[i].p=i;
}
sort(sum+1,sum+2*n+1);
sort(A+1,A+n*2+1,cmp);A[0].z=1;
sort(H+1,H+n+1,cmp);H[0].z=1;
A[0].x=A[1].x;H[0].x=H[1].x;
for(int i=1;i<=2*n;i++)
{
if(A[i].x==A[i-1].x)A[i].z=A[i-1].z;
else if(A[i].x==A[i-1].x+1)A[i].z=A[i-1].z+1;
else A[i].z=A[i-1].z+2;
suma[A[i].z]=A[i].x;
}
for(int i=1;i<=n;i++)
{
if(H[i].x==H[i-1].x)H[i].z=H[i-1].z;
else H[i].z=H[i-1].z+1;
sumh[H[i].z]=H[i].x;
}
for(int i=1;i<=2*n;i++)s1[A[i].p]=A[i].z;
for(int i=1;i<=n;i++)s2[H[i].p]=H[i].z;
build(1,A[n*2].z+1);
for(int i=1;i<=n;i++)
{
change(1,s1[i*2-1],s1[i*2],s2[i]);
}
find(1,1,A[n*2].z+1);
printf("%lld\n",ans);
return 0;
}
```
by xiaogongzhu @ 2019-01-31 19:34:09
%%% 本蒟蒻看都看不懂
by Goldbach @ 2019-01-31 20:08:05