题目链接：
POJ - 1177 or HDU - 1828
题目大意：
以左下点和右上点的形式给出 n 个矩形，求这些矩形相互覆盖后，还能看到的周长。
数据范围：
解题思路：
和矩形并面积、矩形交面积类似。
以下所描述变量或数组含义同代码。
除了维护 总区间被覆盖长度之外
len
，还要维护一个 总区间的线段条数
num
。另外，还需要两个辅助的变量
cl和cr
，分别表示当前区间的左右端点是否被覆盖(一种方法，要get到)。
在通过左右儿子更新父亲的时候，如果左儿子的右端点 和 右儿子的左端点 同时被覆盖了，那么
tree[father].num=tree[lson].num+tree[rson].num−1
。这个稍微想想就明白了。
除了求 总区间线段条数，还要求 当前这条线段覆盖后的总区间长度
len
与 当前这条线段覆盖前的总区间长度
prelen
的 差值的绝对值。求这些是有用的。
还是看图来得更直白！
给如下
3
个矩形，
然后开始一步一步求周长
ans
。
第一步：
初始总区间覆盖长度
prelen
为0，扫到第一条线段的时候，当前总区间覆盖长度
len为4
，周长
ans
加上
∣len−
prelen
∣
，即
ans+=4
。除此之外，还要加上
2∗(后面那条线段高度−当前这条线段高度)
，即
ans+=tree[1].num∗2∗(seg[i+1].h−seg[i].h)
，总区间
tree[1].num=1
，所以
ans+=2
。
这就是求并周长的方法，记住！
第二步：
扫到第二条线段，总区间覆盖长度
len为7
，
prelen为4
，总区间线段条数
tree[1].num为2
，
∣len−prelen∣=3
，
tree[1].num∗2∗(seg[i+1].h−seg[i].h)=4
，所以
ans+=7
。
第三步：
len=8，prelen=7
，
∣len−prelen∣=1
；
tree[1].num=1
，
tree[1].num∗2∗(seg[i+1].h−seg[i].h)=2
，
ans+=3
。
第四步：
∣len−prelen∣=1
.
tree[1].num∗2∗(seg[i+1].h−seg[i].h)=2
.
ans+=3
.
第五步：
ans+=4
.
第六步：
ans+=5
.
最后，
ans=28
。over！
当个板子存起来，忘了就多看看。
详见代码：
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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 5010;
int n, m, k;
struct Segment {
int xl, xr;
int h;
int flag;
Segment() {}
Segment(int a, int b, int c, int d) : xl(a), xr(b), h(c), flag(d) {}
bool friend operator < (Segment a, Segment b) {
if(a.h == b.h) return a.flag > b.flag;
else return a.h < b.h;
}
}seg[2 * MaxN + 5];
int x[2 * MaxN + 5];
struct segtree {
int l, r;
int num;
//当前节点所管辖区间中的 线段条数
int len;
//当前节点所管辖区间的 被覆盖长度
bool cl, cr;
//分别表示当前区间的左右端点是否被覆盖,1被覆盖,0反之
}tree[8 * MaxN + 5];
int cover[8 * MaxN + 5]; //cover[rt]表示rt节点所管辖区间被覆盖了多少次,即lazy数组
void Build(int rt, int l, int r) { //建树
tree[rt].l = l, tree[rt].r = r;
tree[rt].num = 0; tree[rt].len = 0;
if(l == r - 1) return;
int mid = (l + r) >> 1;
Build(rt << 1, l, mid);
Build(rt << 1 | 1, mid, r);
}
int bin_search(int val) { //查找x数组中大于等于val的最小位置
int l = 1, r = k;
int res = 0, mid = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(x[mid] >= val) res = mid, r = mid - 1;
else l = mid + 1;
}
return res;
}
void push_up(int rt) {
if(cover[rt] > 0) {
//若当前区间被覆盖,则更新节点信息
tree[rt].len = x[tree[rt].r] - x[tree[rt].l];
tree[rt].num = 1;
tree[rt].cl = 1; tree[rt].cr = 1;
return;
}
if(tree[rt].l == tree[rt].r - 1) {
//若为叶子节点,覆盖长度len,线段条数num都为0;左右端点自然没有被覆盖
tree[rt].len = 0; tree[rt].num = 0;
tree[rt].cl = 0; tree[rt].cr = 0;
return;
}
//否则,由左右儿子更新当前节点信息
tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;
tree[rt].cl = tree[rt << 1].cl;
tree[rt].cr = tree[rt << 1 | 1].cr;
tree[rt].num = tree[rt << 1].num + tree[rt << 1 | 1].num - (tree[rt << 1].cr && tree[rt << 1 | 1].cl);
//这一步需要稍微想一想
}
void update(int rt, int L, int R, int f) {
if(L <= tree[rt].l && tree[rt].r <= R) {
cover[rt] += f;
push_up(rt);
return;
}
if(tree[rt].l == tree[rt].r - 1) return;
int mid = (tree[rt].l + tree[rt].r) >> 1;
if(L <= mid) update(rt << 1, L, R, f);
if(R > mid) update(rt << 1 | 1, L, R, f);
push_up(rt);
}
int main()
{
while(scanf("%d", &n) != EOF)
{
m = 0;
for(int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
x[++m] = x1;
seg[m] = Segment(x1, x2, y1, 1);
x[++m] = x2;
seg[m] = Segment(x1, x2, y2, -1);
}
sort(x + 1, x + m + 1);
sort(seg + 1, seg + m + 1);
k = unique(x + 1, x + m + 1) - x; //去除数组x中的重复元素,即离散化
Build(1, 1, k);
int ans = 0;
int pre_len = 0; //之前的总区间的 被覆盖总长度
for(int i = 1; i <= m; i++) {
int L = bin_search(seg[i].xl);
int R = bin_search(seg[i].xr);
update(1, L, R, seg[i].flag);
ans += abs(tree[1].len - pre_len);
pre_len = tree[1].len;
if(i < m)
ans += tree[1].num * 2 * (seg[i + 1].h - seg[i].h);
}
printf("%dn", ans);
memset(x, 0, sizeof(x));
}
return 0;
}
降阶版：矩形并面积 and 矩形交面积
最后
以上就是追寻秀发最近收集整理的关于POJ - 1177/HDU - 1828 Picture(线段树-矩形并周长)的全部内容，更多相关POJ内容请搜索靠谱客的其他文章。
发表评论 取消回复