题目描述

在平面内有一些矩形，它们的两条边都平行于坐标轴。

我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。

请问，被奇数个矩形覆盖和被偶数（≤2\leq2）个矩形覆盖的点的面积分别是多少?

实现

显然这题是一道扫描线，不会扫描线的同学先去做这道题。本题解就不讲扫描线是如何实现的了。

由于要奇偶分开输出，我们的线段树就不能像下面的代码一样只维护一个区间长度了。

1
2
3
4
5
6
7
8
void pushup(int now){
	if(tree[now].num){
		tree[now].len=x[tree[now].r+1]-x[tree[now].l];
	}
	else{
		tree[now].len=tree[now*2].len+tree[now*2+1].len;
	}
}

很显然，上面这份代码的 len 要被拆成两个，一个用来存奇数覆盖，一个用来存偶数覆盖。由于要保证奇加上偶的面积等于总面积并，我们需要修改原来的上推函数。

显然，这要分成 33 种情况：

  • 没有覆盖：奇偶都只需要从左右儿子加和就行了。

  • 覆盖的矩形数为奇数：此时当前的奇数长度更多要依赖区间长度计算，于是先算偶数长度。根据偶等于奇（当前覆盖矩形数）加奇（左右儿子），偶数长度是左右儿子奇数长度之和。又由于满足奇偶加和为总面积并，所以奇数长度就等于区间长度减刚刚才算的偶数长度。

  • 覆盖的矩形数为偶数：根据奇等于偶加奇，奇数长度是左右儿子奇数长度之和。同上面的分析，偶数长度是区间长度减刚刚算的奇数长度。

在扫描线的基础上这样修改完上推函数，这道题也就做完了。

提示：记得把空间开大一点！

AC 代码：

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
#include<bits/stdc++.h>
using namespace std;
int x[2000001];
struct segtree{
	int l;
	int r;
	long long len1,len2,num;
};
segtree tree[4000050];
struct defline{
	int xl,xr,y;
	long long num;
};
defline line[4000050];
bool cmp(defline a,defline b){
	return a.y<b.y;
}
void build(int l,int r,int now){
	tree[now].l=l,tree[now].r=r;
	tree[now].len1=0;
	tree[now].len2=0;
	tree[now].num=0;
	if(l==r)return;
	int mid=(l+r)/2;
	build(l,mid,now*2),build(mid+1,r,now*2+1);
	return;
}
void pushup(int now){
	if(tree[now].num==0){
		tree[now].len1=tree[now*2].len1+tree[now*2+1].len1;
		tree[now].len2=tree[now*2].len2+tree[now*2+1].len2;
	}
	else if(tree[now].num%2){
		tree[now].len2=tree[now*2].len1+tree[now*2+1].len1;
		tree[now].len1=x[tree[now].r+1]-x[tree[now].l]-tree[now].len2;
	}
	else{
		tree[now].len1=tree[now*2].len1+tree[now*2+1].len1;
		tree[now].len2=x[tree[now].r+1]-x[tree[now].l]-tree[now].len1;
	}
}
void update(int l,int r,int now,int num){
	if(x[tree[now].r+1]<=l||x[tree[now].l]>=r)return;
	if(x[tree[now].r+1]<=r&&x[tree[now].l]>=l){
		tree[now].num+=num;
		pushup(now);
		return;
	}
	update(l,r,now*2,num);
	update(l,r,now*2+1,num);
	pushup(now);
	return;
}
int main(){
	int n,xlt,xrt,yup,ydown;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>xlt>>ydown>>xrt>>yup;
		x[i*2-1]=xlt;
		x[i*2]=xrt;
		line[i*2-1].xl=xlt;
		line[i*2-1].xr=xrt;
		line[i*2-1].y=ydown;
		line[i*2-1].num=1;
		line[i*2].xl=xlt;
		line[i*2].xr=xrt;
		line[i*2].y=yup;
		line[i*2].num=-1;
	}
	n*=2;
	sort(x+1,x+n+1);
	sort(line+1,line+n+1,cmp);
	int tot=unique(x+1,x+n+1)-x-1;
	build(1,tot-1,1);
	long long ans1=0,ans2=0;
	for(int i=1;i<n;i++){
		update(line[i].xl,line[i].xr,1,line[i].num);
		ans1+=tree[1].len1*(line[i+1].y-line[i].y);
		ans2+=tree[1].len2*(line[i+1].y-line[i].y);
	}
	cout<<ans1<<endl<<ans2<<endl;
    return 0;
}