1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include<bits/stdc++.h>
using namespace std;
int n;
long long c[800001];
long long len[800001];
struct segment{
long long l,r,h;
short type;
}s[200001];
int d[400001];
int zip[400001];
int tot;
inline void add(int t,int l,int r,int x,int y,long long k)
{
if(x<=l&&y>=r)
{
c[t]+=k;
if(c[t])
{
len[t]=zip[r+1]-zip[l];
}
else
{
if(l==r)
{
len[t]=0;
}
else
{
len[t]=len[t<<1]+len[t<<1|1];
}
}
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
{
add(t<<1,l,mid,x,y,k);
}
if(y>mid)
{
add(t<<1|1,mid+1,r,x,y,k);
}
if(!c[t])
{
if(l==r)
{
len[t]=0;
}
else
{
len[t]=len[t<<1]+len[t<<1|1];
}
}
return ;
}
bool cmp(segment a,segment b)
{
return a.h<b.h;
}
long long ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i*2-1].l;
cin>>s[i*2-1].h;
cin>>s[i*2-1].r;
s[i*2-1].type=1;
s[i*2].l=s[i*2-1].l;
s[i*2].r=s[i*2-1].r;
cin>>s[i*2].h;
s[i*2].type=-1;
zip[i*2-1]=s[i*2-1].l;
zip[i*2]=s[i*2-1].r;
}
sort(s+1,s+2*n+1,cmp);
sort(zip+1,zip+2*n+1);
tot=unique(zip+1,zip+2*n+1)-zip-1;
for(int i=1;i<2*n;i++)
{
add(1,1,tot,lower_bound(zip+1,zip+tot+1,s[i].l)-zip,lower_bound(zip+1,zip+tot+1,s[i].r)-zip-1,s[i].type);
ans+=(long long)len[1]*(s[i+1].h-s[i].h);
}
cout<<ans<<endl;
return 0;
}
|