HDU_1828_扫描线求周长(线段树维护)

HDU 1828

  • 从下到上扫一遍如何求出横边与竖边的长度?
  1. 横边
  • 用一个变量存上一次区间横边覆盖总长度.
    这一次的区间横边覆盖总长度-上一次区间横边覆盖总长度=此次扫描的横边周长,取绝对值(可能为负数)

    竖边

  • 线段树维护每个区间覆盖横边的数量(矩形的个数),一个矩形有2个竖边,竖边的长度=下一条横边高度-此条横边高度,所以竖边的周长:2*高度*矩形个数
  • 线段树为了维护一个区间被覆盖横边的数量num,所以还要记录该节点的2个端点是否被覆盖才能确切知道区间中被覆盖横边的数量
    例如 
    1
    2
    3
    [1,10]中,被[1,3][4,5]覆盖,num = 1
    [1,10]中,被[1,2][4,5]覆盖num=2
    [1,10],被[1,5][3,6]覆盖,num=1

扫描线问题还要注意矩形上边下边端点重复的问题,线段树维护不了,

  • 如上边[1,3],
  • 那么区间覆盖次数-1,下边[3,7]区间覆盖次数+1,
  • 3点最后覆盖次数为0,导致统计[1,3]节点是的长度为2,
  • 那么对于此类问题都要才用[)左闭右开,统计区间覆盖长度时+1，就能解决

注意线段树区间范围

  • 线段树如果维护区间有负值,注意>>1和/2的区别,一个是向下取整,/2是向0取整
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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 5005;
const int X = 20007;
const int inf = 1 << 29;
struct edge {
	int l, r;
	int h, f;
	bool operator<(const edge& temp )const {
		return h < temp.h;
	}
}e[N<<1];
struct node {
	int l, r;
	int len; int add;
	int num;
	bool lc, rc;
}q[X<<2];
#define ls i<<1
#define rs i<<1|1
void pushup(int i) {
	if (q[i].add) { //覆盖次数
		q[i].len = q[i].r - q[i].l + 1;
		q[i].lc = q[i].rc = 1;//左右端点被覆盖
		q[i].num = 1;
	}
	else if (q[i].l == q[i].r) {
		q[i].len = 0;
		q[i].lc = q[i].rc = 0;
		q[i].num = 0;
	}
	else {
		q[i].len = q[ls].len + q[rs].len;
		q[i].lc = q[ls].lc; q[i].rc = q[rs].rc;
		q[i].num = q[ls].num + q[rs].num - (q[ls].rc & q[rs].lc);
	}
}
void build(int i,int l,int r) {
	q[i].l = l; q[i].r = r;
	q[i].add = q[i].len = 0;
	q[i].rc = q[i].lc = q[i].num = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void update(int i,int l,int r,int val) {
	if (l == q[i].l && r == q[i].r) {
		q[i].add += val;
		pushup(i);
		return;
	}
	int mid = (q[i].l + q[i].r)>>1; //左移向下取整
	if (r <= mid) update(ls,l,r,val);
	else if (l > mid) update(rs,l,r,val);
	else {
		update(ls,l,mid,val);
		update(rs,mid+1,r,val);
	}
	pushup(i);
}
int main() {
	int n; freopen("a.txt","r",stdin);
	while (cin >> n) {
		int x1, y1, x2, y2, mx = -inf, mn = inf;
		int tot = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			mx = max(mx,max(x1,x2));
			mn = min(mn,min(x1,x2));
			edge& t1 = e[tot]; edge& t2 = e[tot + 1];
			t1.l = t2.l = x1;
			t1.r = t2.r = x2;
			t1.h = y1; t1.f = 1;
			t2.h = y2; t2.f = -1;
			tot += 2;
		}
		sort(e,e+tot);
		int ans = 0;
		int last = 0;
		build(1,mn,mx -1);
		for (int i = 0; i < tot; i++) {
			update(1,e[i].l,e[i].r-1,e[i].f);
			ans += abs(q[1].len - last);
			ans += (e[i + 1].h - e[i].h) * 2 * q[1].num;
			last = q[1].len;
		}
		printf("%d\n",ans);
	}
	return 0;
}