CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
跟着这篇博客复习扫描线+线段树…
Atlantis
求矩形并，即平面上至少被一个矩形覆盖的面积。
离散化: 这些技巧都是老生常谈的了，不然浮点数怎么建树，离散化 x 坐标就可以了。
扫描线: 首先把矩形按 y 轴分成两条边，上边和下边，对 x 轴建树，扫描线可以看成一根平行于 x 轴的直线。从 y=0 开始往上扫，下边表示要计算面积+1，上边表示已经扫过了 −1，直到扫到最后一条平行于 xx 轴的边但是真正在做的时候，不需要完全模拟这个过程，一条一条边地插入线段树就好了。
线段树: 用于动态维护扫描线在往上走时，x 轴哪些区域是有合法面积的。这种线段树是不用懒标记的，因为没有查询操作
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
#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaUnion
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll sum;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l < r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
}
ll ask()
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() * 4, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].sum * (s[i + 1].h - s[i].h);
}
return ans;
}
};
int main()
{
for (int kase = 0, n; ~scanf("%d", &n) && n;)
{
AreaUnion a;
for (int i = 0; i < n; ++i)
{
ll l, b, r, t;
scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
a.add(l, b, r, t);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++kase, a.ask());
}
}
覆盖的面积
求矩形交，即平面上至少被覆盖两次的面积。线段树上维护被覆盖一次的长度和被覆盖两次的长度。
前面的与矩形面积并类似，不同的是要考虑至少覆盖一次 one 和至少覆盖两次 two 的更新。
尤其是当前被覆盖了一次的时候，由于没有 down 操作，父亲节点的信息是没有同步到儿子节点的，这样的话 up 就要考虑了。
父亲被记录覆盖了一次，但是如果儿子被覆盖过，这些操作都是在这个父亲这个大区间上的，就相当于父亲区间被覆盖了至少两次，所以 two 和 one 都要更新。
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
#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaIntersection
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll one, two;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
if (v[rt].cnt == 0)
{
v[rt].one = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
v[rt].two = l != r ? v[rt << 1].two + v[rt << 1 | 1].two : 0;
}
else
{
v[rt].one = rk[r + 1] - rk[l];
if (v[rt].cnt > 1)
v[rt].two = rk[r + 1] - rk[l];
else
v[rt].two = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
}
}
ll ask()
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() * 4, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].two * (s[i + 1].h - s[i].h);
}
return ans;
}
};
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
AreaIntersection a;
scanf("%d", &n);
for (ll l, b, r, t; n--;)
{
scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
a.add(l, b, r, t);
}
printf("%.2lf\n", a.ask());
}
}
Picture
求矩形周长并。
解法一
可以用类似矩形面积并的办法，不过这次我们，不算面积罢了。
需要注意的是，由于周长的线会被重复覆盖，每次需要和上一次的作差。
但是这样仅仅是 x 轴的，不过可以再对 y 轴做一次加起来就可以了。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct HalfPerimeter
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h != rhs.h ? h < rhs.h : f > rhs.f; }
};
struct Node
{
int cnt;
ll sum;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
ll add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int L, int R, int c, int l, int r, int rt = 1)
{
if (L <= l && r <= R)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (L <= m)
upd(L, R, c, l, m, rt << 1);
if (R > m)
upd(L, R, c, m + 1, r, rt << 1 | 1);
}
v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l != r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
}
ll ask()
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() << 2, Node());
ll ans = 0;
for (int i = 0; i < s.size(); ++i)
{
ll last = v[1].sum;
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += abs(v[1].sum - last);
}
return ans;
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
HalfPerimeter x, y;
for (int i = 0, l, b, r, t; i < n; ++i)
{
scanf("%d%d%d%d", &l, &b, &r, &t);
x.add(l, b, r, t);
y.add(b, l, t, r);
}
printf("%d\n", x.ask() + y.ask());
}
}
解法二
也可以只对 x 轴做一次扫描线，只要同时维护 y 轴竖线（就是求矩形面积并的时候的高）的个数 vtl。
需要的注意的是竖线重合的情况，需要再开变量 lbd、rbd 来判断重合，避免重复计算。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct Perimeter
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll sum, vtl, lbd, rbd;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
if (v[rt].cnt)
{
v[rt].lbd = v[rt].rbd = 1;
v[rt].sum = rk[r + 1] - rk[l];
v[rt].vtl = 2;
}
else if (l == r)
v[rt].sum = v[rt].vtl = v[rt].lbd = v[rt].rbd = 0;
else
{
v[rt].lbd = v[rt << 1].lbd;
v[rt].rbd = v[rt << 1 | 1].rbd;
v[rt].sum = v[rt << 1].sum + v[rt << 1 | 1].sum;
v[rt].vtl = v[rt << 1].vtl + v[rt << 1 | 1].vtl;
if (v[rt << 1].rbd && v[rt << 1 | 1].lbd)
v[rt].vtl -= 2;
}
}
ll ask()
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() << 2, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
ll pre = v[1].sum;
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].vtl * (s[i + 1].h - s[i].h) + abs(v[1].sum - pre);
}
return ans + abs(v[1].sum);
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
Perimeter p;
for (int i = 0, l, b, r, t; i < n; ++i)
{
scanf("%d%d%d%d", &l, &b, &r, &t);
p.add(l, b, r, t);
}
printf("%d\n", p.ask());
}
}