Picture【HDU - 1828】【扫描线】

174 阅读 0 评论 115 点赞

我是靠谱客的博主大力柜子，这篇文章主要介绍Picture【HDU - 1828】【扫描线】，现在分享给大家，希望可以做个参考。

题目链接

这道题求的是这些可能存在重叠的小方块可能构成的合成方块的周长的值是多少，有简单却会很复杂的做法就是去跑纵向和横向两次的扫描线，求得最后的两个周长和，但是这样的做法未免显得复杂了，我们完全可以只跑一次线段树（扫描线）来做到这样的要求。

思路：问题就是我们得去知道有多少个可以竖起来的边，也就是有在两条扫描线之间，有多少个独立的方块在其中？我们求得独立方块数，最后乘以2就是最后的竖的边的数量，那么在解决竖直边上的这个问题我们就首先解决了。接下去就是求解横向的边的长度，我们每次的扫描线，也就代表着目前处理到的线上有多长的区间，那么我们求一个与上一个状态的差值，就是目前没被覆盖的边的增加出来的周长了。于是，我们加起来就会得到最后的总的周长了。

复制代码

1 #include <iostream>

2 #include <cstdio>

3 #include <cmath>

4 #include <string>

5 #include <cstring>

6 #include <algorithm>

7 #include <limits>

8 #include <vector>

9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #define lowbit(x) ( x&(-x) )
 14 #define pi 3.141592653589793
 15 #define e 2.718281828459045
 16 #define INF 0x3f3f3f3f
 17 #define HalF (l + r)>>1
 18 #define lsn rt<<1
 19 #define rsn rt<<1|1
 20 #define Lson lsn, l, mid
 21 #define Rson rsn, mid+1, r
 22 #define QL Lson, ql, qr
 23 #define QR Rson, ql, qr
 24 #define myself rt, l, r
 25 using namespace std;
 26 typedef unsigned long long ull;
 27 typedef long long ll;
 28 const int maxN = 1e4 + 7;
 29 int N, tot, X[maxN], _UP;
 30 struct node
 31 {
 32
int lx, rx, y, val;
 33
node(int a=0, int b=0, int c=0, int d=0):lx(a), rx(b), y(c), val(d) {}
 34 }line[maxN];
 35 bool cmp(node e1, node e2) { return e1.y < e2.y; }
 36 struct tree
 37 {
 38
int sum, siz, num;
 39
bool lc, rc;
 40
tree(int a=0, int b=0, int f=0, bool c=false, bool d=false):sum(a), siz(b), num(f), lc(c), rc(d) {}
 41
void clear() { sum = siz = num = 0; lc = rc = false; }
 42 }t[maxN<<2];
 43 inline void buildTree(int rt, int l, int r)
 44 {
 45 
t[rt].clear();
 46
if(l == r) return;
 47
int mid = HalF;
 48 
buildTree(Lson);
 49 
buildTree(Rson);
 50 }
 51 inline void pushup(int rt, int l, int r)
 52 {
 53
if(t[rt].siz)
 54 
{
 55
t[rt].sum = X[r + 1] - X[l];
 56
t[rt].lc = t[rt].rc = true;
 57
t[rt].num = 1;
 58 
}
 59
else if(l == r)
 60 
{
 61
t[rt].sum = t[rt].num = 0;
 62
t[rt].lc = t[rt].rc = false;
 63 
}
 64
else
 65 
{
 66
t[rt].sum = t[lsn].sum + t[rsn].sum;
 67
t[rt].lc = t[lsn].lc;
t[rt].rc = t[rsn].rc;
 68
t[rt].num = t[lsn].num + t[rsn].num - (t[lsn].rc && t[rsn].lc);
 69 
}
 70 }
 71 inline void update(int rt, int l, int r, int ql, int qr, int val)
 72 {
 73
if(ql <= l && qr >= r)
 74 
{
 75
t[rt].siz += val;
 76 
pushup(myself);
 77
return;
 78 
}
 79
int mid = HalF;
 80
if(qr <= mid) update(QL, val);
 81
else if(ql > mid) update(QR, val);
 82
else { update(QL, val); update(QR, val); }
 83 
pushup(myself);
 84 }
 85 inline void init()
 86 {
 87
tot = 0;
 88 }
 89 int main()
 90 {
 91
while(scanf("%d", &N) != EOF)
 92 
{
 93 
init();
 94
int lx, ly, rx, ry;
 95
for(int i=1; i<=N; i++)
 96 
{
 97
scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
 98
line[++tot] = node(lx, rx, ly, 1);
 99
X[tot] = lx;
100
line[++tot] = node(lx, rx, ry, -1);
101
X[tot] = rx;
102 
}
103
sort(X + 1, X + tot + 1);
104
sort(line + 1, line + tot + 1, cmp);
105
_UP = (int)(unique(X + 1, X + tot + 1) - X - 1);
106
buildTree(1, 1, _UP);
107
int ans = 0, las = 0;
108
for(int i=1, l, r; i<tot; i++)
109 
{
110
l = (int)(lower_bound(X + 1, X + _UP + 1, line[i].lx) - X);
111
r = (int)(lower_bound(X + 1, X + _UP + 1, line[i].rx) - X - 1);
112
update(1, 1, _UP, l, r, line[i].val);
113
ans += abs(las - t[1].sum);
114
las = t[1].sum;
115
ans += (line[i + 1].y - line[i].y) * (t[1].num << 1);
116 
}
117
ans += line[tot].rx - line[tot].lx;
118
printf("%dn", ans);
119 
}
120
return 0;
121 }
122 /*
123 7
124 -15 0 5 10
125 -5 8 20 25
126 15 -4 24 14
127 0 -6 16 4
128 2 15 10 22
129 30 10 36 20
130 34 0 40 16
131 ans = 228
132 */

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

1 #include <iostream>

2 #include <cstdio>

3 #include <cmath>

4 #include <string>

5 #include <cstring>

6 #include <algorithm>

7 #include <limits>

8 #include <vector>

9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #define lowbit(x) ( x&(-x) )
 14 #define pi 3.141592653589793
 15 #define e 2.718281828459045
 16 #define INF 0x3f3f3f3f
 17 #define HalF (l + r)>>1
 18 #define lsn rt<<1
 19 #define rsn rt<<1|1
 20 #define Lson lsn, l, mid
 21 #define Rson rsn, mid+1, r
 22 #define QL Lson, ql, qr
 23 #define QR Rson, ql, qr
 24 #define myself rt, l, r
 25 using namespace std;
 26 typedef unsigned long long ull;
 27 typedef long long ll;
 28 const int maxN = 1e4 + 7;
 29 int N, tot, X[maxN], _UP;
 30 struct node
 31 {
 32
int lx, rx, y, val;
 33
node(int a=0, int b=0, int c=0, int d=0):lx(a), rx(b), y(c), val(d) {}
 34 }line[maxN];
 35 bool cmp(node e1, node e2) { return e1.y < e2.y; }
 36 struct tree
 37 {
 38
int sum, siz, num;
 39
bool lc, rc;
 40
tree(int a=0, int b=0, int f=0, bool c=false, bool d=false):sum(a), siz(b), num(f), lc(c), rc(d) {}
 41
void clear() { sum = siz = num = 0; lc = rc = false; }
 42 }t[maxN<<2];
 43 inline void buildTree(int rt, int l, int r)
 44 {
 45 
t[rt].clear();
 46
if(l == r) return;
 47
int mid = HalF;
 48 
buildTree(Lson);
 49 
buildTree(Rson);
 50 }
 51 inline void pushup(int rt, int l, int r)
 52 {
 53
if(t[rt].siz)
 54 
{
 55
t[rt].sum = X[r + 1] - X[l];
 56
t[rt].lc = t[rt].rc = true;
 57
t[rt].num = 1;
 58 
}
 59
else if(l == r)
 60 
{
 61
t[rt].sum = t[rt].num = 0;
 62
t[rt].lc = t[rt].rc = false;
 63 
}
 64
else
 65 
{
 66
t[rt].sum = t[lsn].sum + t[rsn].sum;
 67
t[rt].lc = t[lsn].lc;
t[rt].rc = t[rsn].rc;
 68
t[rt].num = t[lsn].num + t[rsn].num - (t[lsn].rc && t[rsn].lc);
 69 
}
 70 }
 71 inline void update(int rt, int l, int r, int ql, int qr, int val)
 72 {
 73
if(ql <= l && qr >= r)
 74 
{
 75
t[rt].siz += val;
 76 
pushup(myself);
 77
return;
 78 
}
 79
int mid = HalF;
 80
if(qr <= mid) update(QL, val);
 81
else if(ql > mid) update(QR, val);
 82
else { update(QL, val); update(QR, val); }
 83 
pushup(myself);
 84 }
 85 inline void init()
 86 {
 87
tot = 0;
 88 }
 89 int main()
 90 {
 91
while(scanf("%d", &N) != EOF)
 92 
{
 93 
init();
 94
int lx, ly, rx, ry;
 95
for(int i=1; i<=N; i++)
 96 
{
 97
scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
 98
line[++tot] = node(lx, rx, ly, 1);
 99
X[tot] = lx;
100
line[++tot] = node(lx, rx, ry, -1);
101
X[tot] = rx;
102 
}
103
sort(X + 1, X + tot + 1);
104
sort(line + 1, line + tot + 1, cmp);
105
_UP = (int)(unique(X + 1, X + tot + 1) - X - 1);
106
buildTree(1, 1, _UP);
107
int ans = 0, las = 0;
108
for(int i=1, l, r; i<tot; i++)
109 
{
110
l = (int)(lower_bound(X + 1, X + _UP + 1, line[i].lx) - X);
111
r = (int)(lower_bound(X + 1, X + _UP + 1, line[i].rx) - X - 1);
112
update(1, 1, _UP, l, r, line[i].val);
113
ans += abs(las - t[1].sum);
114
las = t[1].sum;
115
ans += (line[i + 1].y - line[i].y) * (t[1].num << 1);
116 
}
117
ans += line[tot].rx - line[tot].lx;
118
printf("%dn", ans);
119 
}
120
return 0;
121 }
122 /*
123 7
124 -15 0 5 10
125 -5 8 20 25
126 15 -4 24 14
127 0 -6 16 4
128 2 15 10 22
129 30 10 36 20
130 34 0 40 16
131 ans = 228
132 */