扫描线

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

#include <iostream>
#include <algorithm>
#include <queue>
#define lc u<<1
#define rc u<<1|1
#define ll long long
using namespace std;
const ll maxn=2e5+5;
int v[maxn];// 存所有的x轴坐标 
struct L{
	int y;//x轴的y坐标
	int x1,x2;//在y水平线上x轴的坐标
	int state;//这个水平线是矩阵的上边还是下边 ,1为下边，-1为上边	 
}line[maxn];//按y轴从小到大排序，因为扫描线是从下向上扫描的 
bool operator <(const L &a,const L &b){
	return a.y<b.y;
} 
struct Node {//线段树 
	int l,r;//节点的左右区间 
	int cover;//这个区间被覆盖的次数 ,就被多少个不同的矩阵覆盖
	//因为不同的矩阵有不同的上边...
	//在一个矩阵结束后可能还有别的矩阵覆盖着这个区域 
	ll len;//这个区间中有贡献的区间长度，贡献值不一定是r-l 
}tr[maxn<<3];//注意这个树的大小

void updata(int u){
	if (tr[u].cover){//这个区间被完全覆盖了
	//则这个区间的贡献值 len=r-l 
		tr[u].len=tr[u].r-tr[u].l;
	}else {
		//这个区间没有被完全覆盖，贡献值等于子区间贡献值的和
		tr[u].len=tr[lc].len+tr[rc].len;
	}
}
void build (int u,int l,int r){
	
	//树上u节点的左右区间，即这个节点负责的x轴的范围
	// v中存放的x轴的坐标从小到达排序，
	//因为不是每一个x轴的坐标都有用，所以使用l，r存放有用的坐标就可以了
	//而不需要像之前那样，将节点的区间完全的二分到[1,1],[2,2].....
	//例如有两个矩阵x轴分别为(100,200)(150,250)。
	//则节点区间最多分为[100,150],[150,200],[200,250]，
	//例如[100,120]这个区间是没用的,她不可能只覆盖[100,120],而不覆盖[120，200]的区间 
	tr[u].l=v[l],tr[u].r=v[r];
	
	if(r-l<=1){
		return ;
	} 
	int m=(l+r)>>1;
	build (lc,l,m);
	build (rc,m,r);
}

void modify(int l,int r,int z,int u){//区修 
	if (l<=tr[u].l&&r>=tr[u].r){
		tr[u].cover+=z;//cover表示这个节点的区间是否被覆盖
		//cover发生了变化自然要进行维护 
		//每当一个z=-1表示有一个矩阵结束，但任有可能有别的矩阵覆盖着 
		updata(u); 
		return ;
	}
	//不能再区l，r的中间值进行比较，原因看build中的注释 
	if (l<tr[lc].r){
		modify(l,r, z,lc);
	}
	if (r>tr[rc].l){
		modify(l,r, z,rc);
	}
	updata(u);
}

int main ()
{
	int n,a,b,c,d;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a>>b>>c>>d;
		if (a>c){
			swap(a,c);
		}
		v[i]=a,v[i+n]=c;//存储每个矩阵的x轴区间 
		line[i]={b,a,c,1},line[i+n]={d,a,c,-1};//存储每个矩阵的下边和上边 
	} 
	
	sort(v+1,v+1+(n<<1));
	sort (line+1,line+1+(n<<1));
	
	build (1,1,n<<1);
	unsigned long long ans=0;
	for (int i=1;i<=n<<1;i++){
		ans+=tr[1].len*(line[i].y-line[i-1].y);//这两句话的顺序不得更改！！！
		modify(line[i].x1,line[i].x2,line[i].state,1);
	}
	cout<<ans<<endl;
	return 0;	
}