扫描线学习笔记

0. 写在前面

扫描线好闪，拜谢扫描线

1. 问题的引入

在一个二维的坐标系上，给出多个矩形，求他们的面积并

2. 问题的分析

假设我们有这么一张图

你要求这三个矩形的面积并，可以考虑容斥原理，但这样会 TLE

但总之，他最终的结果是围成了一个多边形

那你不妨考虑，重新分割这个最终的图形

那这样你就很会求了。

考虑有一条线，从下往上扫描，如果遇到矩形的一条边就分割一次，OI Wiki 给出了一个很优秀的动图：

那么，你即是要考虑矩形的下端在哪里，矩形的上端在哪里，矩形的高是扫描线扫描的距离。我们使用线段树维护矩形的长，给每个矩形的上下边进行标记。下面标记为 \(1\) ， 上面标记为 \(-1\)，然后乘一下就好了。

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXN 1000001
#define int long long
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define mid(l, r) ((l + r) >> 1)

using namespace std;

int lazy[MAXN << 3]; // 用于标记某条线段出现的次数
int s[MAXN << 3];
struct { int l, r, sum; } 	  sgmt[MAXN << 3];
struct node{ 
	int d, y1, y2, flag; 
	bool operator < (const node& x) const { return this->d < x.d;}
	node(int d, int y1, int y2, int flag) {	this->d = d, this->y1 = y1, this->y2 = y2, this->flag = flag; }
	node() {}
} point[MAXN << 3];

inline void pushup(int now) {
	if(lazy[now] > 0)  sgmt[now].sum = sgmt[now].r       - sgmt[now].l;
	else		       sgmt[now].sum = sgmt[ls(now)].sum + sgmt[rs(now)].sum;
}

void build(int now, int l, int r) {
	if(r - l > 1) sgmt[now].l = s[l], sgmt[now].r = s[r], build(ls(now), l, mid(l, r)), build(rs(now), mid(l, r), r), pushup(now);
	else 		  sgmt[now].l = s[l], sgmt[now].r = s[r], sgmt[now].sum = 0;
}

void upd(int now, int y1, int y2, int flag) {
	if(sgmt[now].l == y1 && sgmt[now].r == y2) lazy[now] += flag, pushup(now);
	else {
		if(sgmt[ls(now)].r > y1)   upd(ls(now), y1, min(sgmt[ls(now)].r, y2), flag);
		if(sgmt[rs(now)].l < y2)   upd(rs(now), max(sgmt[rs(now)].l, y1), y2, flag);
		pushup(now);		
	}
}
int n, ans;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0, x, y, u, v; i < n; ++ i) {
		cin >> x >> y >> u >> v;
		point[i] = {x, y, v, 1}, point[i + n] = {u, y, v, -1};
		s[i + 1] = y, s[i + 1 + n] = v;
	}
	sort(s + 1, s + rs(n)), sort(point, point + ls(n));
	build(1, 1, ls(n));
	upd(1, point[0].y1, point[0].y2, point[0].flag);
	for(int i = 1; i < ls(n); ++ i) {
		ans += (point[i].d - point[i - 1].d) * sgmt[1].sum;
		upd(1, point[i].y1, point[i].y2, point[i].flag);
	}
	cout << ans;
}