扫描线+线段树

上次写了个的扫描线，扫描线的其实可以再优化，今天来说说线段树优化的扫描线。

扫描线的思路很简单，设有多个矩形，求面积并的时候，可以将每个矩形用两个四元组表示，，其中是矩形的的左下角和右上角横坐标的其中一个，是左下角和右上角的两个纵坐标，有两个值，1和-1，含义是从左向右扫描的时候的入边和出边。扫描的时候第一次碰到的就是入边，另外一个是出边，因为是从左向右扫描，所以坐标小的是入边。然后我们就得到了个四元组，将他们按照从小到大排序。然后将所有的坐标放入一个数组中，排序去重，离散化。之前的做法是用一个数组的每个值去维护一个区间，这样每次更新的时候需要扫一遍数组，求解的时候也扫一遍，其实可以用线段树去维护这样一个区间。

线段树维护两个值，当前区间被覆盖的次数，和区间内的被覆盖过的边的长度和，可以再多一个，表示当前区间的长度，方便计算。如果当前区间被覆盖了，显然长度和，如果没有覆盖就是，更新的时候，由于有入边就有出边，所以前面的一定会被后面的抵消掉，就用不到标记下传了。

注意：一定是先计算再更新。

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
struct p{
	int x, y1, y2, mark;
} a[N];
int x[N], y[N];
int dy[N];
int len;
typedef struct SegementTree{
	int l[N * 4];
	int r[N * 4];
	int sum[N * 4];
	int cnt[N * 4];
	int length[N * 4];
	void build(int ll, int rr, int k){
		l[k] = ll;
		r[k] = rr;
		sum[k] = 0;
		cnt[k] = 0;
		if (ll == rr){
			length[k] = dy[ll + 1] - dy[ll];
			return;
		}
		int mid = (ll + rr) / 2;
		build(ll, mid, k << 1);
		build(mid + 1, rr, k << 1 | 1);
		length[k] = length[k << 1] + length[k << 1 | 1];
	}
	void update(int ll, int rr, int k, int mark){
		if (l[k] >= ll && r[k] <= rr){
			cnt[k] += mark;
			sum[k] = cnt[k] ? length[k] : sum[k << 1] + sum[k << 1 | 1];
			
			return ;
		}
		int mid = l[k] + r[k];
		mid /= 2;
		if (ll <= mid)update(ll, rr, k << 1, mark);
		if (rr > mid)update(ll, rr, k << 1 | 1, mark);
		sum[k] = cnt[k] ? length[k] : sum[k << 1] + sum[k << 1 | 1];
	}
} ST;
bool cmp(p& a, p& b){
	return a.x < b.x;
}
int get(int x){
	return lower_bound(dy + 1, dy + 1 + len, x) - dy;
}
ST st;
int main()
{
	freopen("./in.in", "r", stdin);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		scanf("%d %d", x + i, y + i);
		scanf("%d %d", x + i + n, y + i + n);
		a[i].x = x[i];
		a[i].y1 = y[i];
		a[i].y2 = y[i + n];
		a[i].mark = 1;
		a[i + n].x = x[i + n];
		a[i + n].y1 = y[i];
		a[i + n].y2 = y[i + n];
		a[i + n].mark = -1;
		dy[i] = y[i];
		dy[i + n] = y[i + n];
	}
	sort(a + 1, a + 1 + n, cmp);
	sort(dy + 1, dy + 1 + n + n);
	len = unique(dy + 1, dy + 1 + n + n) - dy - 1;
	st.build(1, len - 1, 1);
	int res = 0;
	for (int i = 1; i <= n + n; i++){
                //顺序不能错
		res += st.sum[1] * (a[i].x - a[i - 1].x);
		st.update(get(a[i].y1), get(a[i].y2) - 1, 1, a[i].mark);
	}
	printf("%d\n", res);
	return 0;
}