【HDU】1828-Picture(线段树扫描线）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
typedef long long LL;
const int maxn = 30005;
const int ADD
= 10001;
struct Seg{
int l,r,c,h;
Seg(int l = 0,int r = 0,int h = 0,int c = 0):l(l),r(r),h(h),c(c){};
friend bool operator < (Seg p,Seg q){
return p.h < q.h;
}
}seg[maxn];
struct Node{
int l,r,cover,sum1,sum2;
bool left,right;
int mid(){
return (l + r) >> 1;
}
int len(){
return
r - l + 1;
}
}node[maxn << 2];
int cnt;
void build(int l,int r,int pos){
node[pos].l = l; node[pos].r = r;
node[pos].sum1 = node[pos].sum2 = 0;
node[pos].left = node[pos].right = false;
node[pos].cover = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(l,mid,lson);
build(mid + 1,r,rson);
}
void pushup(int pos){
if(node[pos].cover){
node[pos].sum1 = 2;
node[pos].sum2 = node[pos].len();
node[pos].left = node[pos].right = true;
}
else if(node[pos].len() == 1){
node[pos].sum1 = node[pos].sum2 = node[pos].left = node[pos].right = 0;
}
else{
node[pos].sum1
= node[lson].sum1 + node[rson].sum1;
if(node[lson].right && node[rson].left) node[pos].sum1 -= 2;
node[pos].sum2
= node[lson].sum2 + node[rson].sum2;
node[pos].left
= node[lson].left;
node[pos].right = node[rson].right;
}
}
void update(int l,int r,int pos,int d){
if(l <= node[pos].l && node[pos].r <= r){
node[pos].cover += d;
pushup(pos);
return;
}
int mid = node[pos].mid();
if(l <= mid)
update(l,r,lson,d);
if(r
> mid)
update(l,r,rson,d);
pushup(pos);
return;
}
int main(){
int n;
while(scanf("%d",&n) != EOF){
build(1,30000,1);
cnt = 0;
for(int i = 0; i < n; i++){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
a += ADD; c += ADD;
seg[cnt++] = Seg(a,c,d,1);
seg[cnt++] = Seg(a,c,b,-1);
}
sort(seg,seg + cnt);
LL ans = 0,last = 0;
for(int i = 0; i < cnt; i++){
int l = seg[i].l,r = seg[i].r,c = seg[i].c;
update(l,r - 1,1,c);
if(i < cnt - 1)
ans += node[1].sum1 * (seg[i + 1].h - seg[i].h);
ans += abs(node[1].sum2 - last);
last = node[1].sum2;
}
printf("%I64dn",ans);
}
return 0;
}