POJ - 1177/HDU - 1828 Picture(线段树-矩形并周长)

59 阅读 0 评论 39 点赞

我是靠谱客的博主追寻秀发，最近开发中收集的这篇文章主要介绍POJ - 1177/HDU - 1828 Picture(线段树-矩形并周长)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

POJ - 1177 or HDU - 1828

题目大意：

以左下点和右上点的形式给出 n 个矩形，求这些矩形相互覆盖后，还能看到的周长。

数据范围：

0≤n<5000−10000≤xi,yi≤10000

解题思路：

和矩形并面积、矩形交面积类似。
以下所描述变量或数组含义同代码。
除了维护总区间被覆盖长度之外 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！

当个板子存起来，忘了就多看看。

详见代码：

#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;
}