线段树应用——扫描线

例题1

P5490 【模板】扫描线

例题2

POJ1177 Picture

推荐博客

NCC-79601 Captain’s Log
dzz1537568241

例题1

解题思路

大部分的思路什么的上面的大犇都讲了。
我提几个注意事项：

• 注意空间。在pushup函数中要加以特判l[o]==r[o]，这样数组才能只开4倍。不然，数组应该开8倍（可能会访问叶节点的子节点）
• 线段树的每个叶节点维护的是一段线段而不是点。即线段树的x[o]维护的是一段相邻的点之间的线段。这样的话，代码中的具体的操作就易于理解了。

详细代码

//...IO etc.
const int MAXN = 1e5 + 5;
//从下往上扫 
struct Line {
   ll x1, x2, y, k;
   Line() {}
   Line(ll x1, ll x2, ll y, ll k) : x1(x1), x2(x2), y(y), k(k) {}
   bool operator <(const Line& b)const {return y < b.y;}
}A[MAXN * 2];
int n;
ll lsh[MAXN * 2]; int idl;

struct Segment_tree {
   #define ls o << 1
   #define rs o << 1 | 1
   int l[800005], r[800005], cnt[800005];
   ll len[800005];
   void pushup(int o) {
   	if(cnt[o]) len[o] = lsh[r[o] + 1] - lsh[l[o]];
   	else if(l[o] == r[o]) len[o] = 0;
   	else len[o] = len[ls] + len[rs];
   }
   void build(int o, int L, int R) {
   	l[o] = L, r[o] = R;
   	len[o] = cnt[o] = 0;
   	if(L == R) return;
   	int m = (L + R) >> 1;
   	build(ls, L, m);
   	build(rs, m + 1, R);
   }
   void add(int o, int x, int y, int k) {
   	if(x <= l[o] && r[o] <= y) {
   		cnt[o] += k;
   		pushup(o);
   		return;
   	}
   	int m = (l[o] + r[o]) >> 1;
   	if(x <= m) add(ls, x, y, k);
   	if(y > m) add(rs, x, y, k);
   	pushup(o);
   }
   #undef ls
   #undef rs
}sgtr;
ll ans;
int main() {
   //RS();
   n = read();
   for(rg int i = 1; i <= n; i++) {
   	int x1 = read(), y1 = read(), x2 = read(), y2 = read();
   	A[2 * i - 1] = Line(x1, x2, y1, 1);
   	A[2 * i] = Line(x1, x2, y2, -1);
   	lsh[++idl] = x1; lsh[++idl] = x2;
   }
   sort(A + 1, A + 2 * n + 1);
   sort(lsh + 1, lsh + 1 + idl);
   idl = unique(lsh + 1, lsh + 1 + idl) - lsh - 1;
   for(rg int i = 1; i <= 2 * n; i++) {
   	A[i].x1 = lower_bound(lsh + 1, lsh + 1 + idl, A[i].x1) - lsh;
   	A[i].x2 = lower_bound(lsh + 1, lsh + 1 + idl, A[i].x2) - lsh;
   }
   sgtr.build(1, 1, idl - 1);
   for(rg int i = 1; i < 2 * n; i++) {
   	sgtr.add(1, A[i].x1, A[i].x2 - 1, A[i].k);
   	ans += sgtr.len[1] * (A[i + 1].y - A[i].y); 
   }
   writeln(ans);
   return 0;
}

例题2

解题思路

见上方第1篇博客
TIP：还是要注意数组空间问题

详细代码

//...IO etc.
#include<algorithm>
using namespace std;
const int MAXN = 10005;
int n;
//从下到上扫描 
struct Line {
	int x1, x2, y, k;
	Line(int x1, int x2, int y, int k) : x1(x1), x2(x2), y(y), k(k) {}
	Line() {}
	bool operator < (const Line& b)const {
		if(y == b.y) return k > b.k;
		return y < b.y;
	}
}A[MAXN];
int lsh[MAXN], idl;
	
struct Segment_tree {
	#define ls o << 1
	#define rs o << 1 | 1
	int l[MAXN << 2], r[MAXN << 2], len[MAXN << 2], cnt[MAXN << 2];
	int c[MAXN << 2];//区间覆盖的线段数量
	bool lc[MAXN << 2], rc[MAXN << 2];
	void build(int o, int L, int R) {
		l[o] = L, r[o] = R;
		len[o] = cnt[o] = c[o] = 0; lc[o] = rc[o] = 0;
		if(L == R) return ;
		int m = (L + R) >> 1;
		build(ls, L, m);
		build(rs, m + 1, R);
	}
	void pushup(int o) {
		if(cnt[o]) {
			len[o] = lsh[r[o] + 1] - lsh[l[o]];
			lc[o] = rc[o] = 1;
			c[o] = 1;
		} else if(l[o] == r[o]) {
			len[o] = lc[o] = rc[o] = c[o] = 0;
		} else {
			len[o] = len[ls] + len[rs];
			c[o] = c[ls] + c[rs];
			lc[o] = lc[ls]; rc[o] = rc[rs];
			if(lc[rs] && rc[ls]) c[o]--;
		}
	}
	void add(int o, int x, int y, int k) {
		if(x <= l[o] && r[o] <= y) {
			cnt[o] += k;
			pushup(o);
			return;
		}
		int m = (l[o] + r[o]) >> 1;
		if(x <= m) add(ls, x, y, k);
		if(y > m) add(rs, x, y, k);
		pushup(o);
	}
	#undef ls
	#undef rs
}sg;
int ans;
int main() {
	//RS();
	n = read();
	for(rg int i = 1; i <= n; i++) {
		int x1 = read(), y1 = read(), x2 = read(), y2 = read();
		lsh[++idl] = x1, lsh[++idl] = x2;
		A[i * 2 - 1] = Line(x1, x2, y1, 1);//下边
		A[i * 2] = Line(x1, x2, y2, -1); 
	}
	n <<= 1;
	sort(lsh + 1, lsh + 1 + idl);
	idl = unique(lsh + 1, lsh + 1 + idl) - lsh - 1;
	sort(A + 1, A + 1 + n);
	for(rg int i = 1; i <= n; i++) 
		A[i].x1 = lower_bound(lsh + 1, lsh + 1 + idl, A[i].x1) - lsh,
		A[i].x2 = lower_bound(lsh + 1, lsh + 1 + idl, A[i].x2) - lsh;
	sg.build(1, 1, idl - 1);
	int llen = 0;
	for(rg int i = 1; i < n; i++) {
		sg.add(1, A[i].x1, A[i].x2 - 1, A[i].k);
		ans += Abs(llen - sg.len[1]);
		llen = sg.len[1];
		
		ans += 2 * sg.c[1] * (A[i + 1].y - A[i].y);
	}
	ans += llen;
	writeln(ans);
	return 0;
}