数据结构 1.0(Data structure 1.0)

扫描线

矩形面积并:

利用横线所截取的长度乘以纵向的差.   

这里特别注意一下线段树中最底层表示的是一个点,但长度中需要维护线段.  

所以不妨让线段树中的 $\mathrm{[l,r]}$ 区间实际维护 $\mathrm{[l, r+1)}$ 这条线段.                       

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N  200009 
#define ll long long 
#define pb push_back 
#define ls now << 1 
#define rs now << 1 | 1   
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
struct Line {
	int x1, x2, y, d;  
	Line(int x1 = 0, int x2 = 0, int y = 0, int d = 0):x1(x1), x2(x2), y(y), d(d) {}  
}a[N];
int n , cnt , len[N << 2], A[N << 2], tot ; 
struct data {
	int sum, tag, l, r; 
	data() { sum = tag = l = r = 0; } 
}s[N << 2];  
void build(int l, int r, int now) {
	s[now].l = l, s[now].r = r;   
	if(l == r) return ; 
	int mid = (l + r) >> 1; 
	build(l, mid, ls), build(mid + 1, r, rs); 
}
void pushup(int now) {
	if(s[now].tag) 
		len[now] = A[s[now].r + 1] - A[s[now].l];    
	else {
		if(s[now].l != s[now].r) 
			len[now] = len[ls] + len[rs];  
		else len[now] = 0; 
	}
}    
void update(int l, int r, int now, int L, int R, int v) {
	if(l >= L && r <= R) {
		s[now].tag += v;  
		pushup(now); 
		return ; 
	}
	int mid = (l + r) >> 1;  
	if(L <= mid)  update(l, mid, ls, L, R, v); 
	if(R > mid)   update(mid + 1, r, rs, L, R, v); 
	pushup(now); 
}
bool cmp(Line i, Line j) { return i.y < j.y; } 
int main() {
	// setIO("input"); 
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) {
		int x[2], y[2]; 
		scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);   
		a[++ cnt] = Line(x[0], x[1], y[0], 1);  
		a[++ cnt] = Line(x[0], x[1], y[1], -1);    
		// 离散化横坐标即可.  
		A[++ tot] = x[0], A[++ tot] = x[1];  
	}
	sort(A + 1, A + 1 + tot); 
	tot = unique(A + 1, A + 1 + tot) - A - 1;    
	for(int i = 1; i <= cnt ; ++ i) {
		a[i].x1 = lower_bound(A + 1, A + 1 + tot, a[i].x1) - A; 
		a[i].x2 = lower_bound(A + 1, A + 1 + tot, a[i].x2) - A;   
	}   
	sort(a + 1, a + 1 + cnt, cmp);       
	// int pre = a[1].y;  
	build(1, tot , 1);  
	ll ans = 0; 
	for(int i = 1; i <= cnt ; ++ i) {        
		update(1, tot, 1, a[i].x1, a[i].x2 - 1, a[i].d);     
		ans += 1ll * len[1] * (a[i + 1].y - a[i].y);      
	}
	printf("%lld", ans); 
	return 0; 
}
————————

Scan line

Rectangular area and:

Multiply the length intercepted by the horizontal line by the longitudinal difference

In particular, the bottom layer of the line segment tree represents a point, but the line segment needs to be maintained in the length

So let the $\ mathrm {[l, R]} $interval in the segment tree actually maintain the segment $\ mathrm {[l, R + 1)} $

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N  200009 
#define ll long long 
#define pb push_back 
#define ls now << 1 
#define rs now << 1 | 1   
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
struct Line {
	int x1, x2, y, d;  
	Line(int x1 = 0, int x2 = 0, int y = 0, int d = 0):x1(x1), x2(x2), y(y), d(d) {}  
}a[N];
int n , cnt , len[N << 2], A[N << 2], tot ; 
struct data {
	int sum, tag, l, r; 
	data() { sum = tag = l = r = 0; } 
}s[N << 2];  
void build(int l, int r, int now) {
	s[now].l = l, s[now].r = r;   
	if(l == r) return ; 
	int mid = (l + r) >> 1; 
	build(l, mid, ls), build(mid + 1, r, rs); 
}
void pushup(int now) {
	if(s[now].tag) 
		len[now] = A[s[now].r + 1] - A[s[now].l];    
	else {
		if(s[now].l != s[now].r) 
			len[now] = len[ls] + len[rs];  
		else len[now] = 0; 
	}
}    
void update(int l, int r, int now, int L, int R, int v) {
	if(l >= L && r <= R) {
		s[now].tag += v;  
		pushup(now); 
		return ; 
	}
	int mid = (l + r) >> 1;  
	if(L <= mid)  update(l, mid, ls, L, R, v); 
	if(R > mid)   update(mid + 1, r, rs, L, R, v); 
	pushup(now); 
}
bool cmp(Line i, Line j) { return i.y < j.y; } 
int main() {
	// setIO("input"); 
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) {
		int x[2], y[2]; 
		scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);   
		a[++ cnt] = Line(x[0], x[1], y[0], 1);  
		a[++ cnt] = Line(x[0], x[1], y[1], -1);    
		// 离散化横坐标即可.  
		A[++ tot] = x[0], A[++ tot] = x[1];  
	}
	sort(A + 1, A + 1 + tot); 
	tot = unique(A + 1, A + 1 + tot) - A - 1;    
	for(int i = 1; i <= cnt ; ++ i) {
		a[i].x1 = lower_bound(A + 1, A + 1 + tot, a[i].x1) - A; 
		a[i].x2 = lower_bound(A + 1, A + 1 + tot, a[i].x2) - A;   
	}   
	sort(a + 1, a + 1 + cnt, cmp);       
	// int pre = a[1].y;  
	build(1, tot , 1);  
	ll ans = 0; 
	for(int i = 1; i <= cnt ; ++ i) {        
		update(1, tot, 1, a[i].x1, a[i].x2 - 1, a[i].d);     
		ans += 1ll * len[1] * (a[i + 1].y - a[i].y);      
	}
	printf("%lld", ans); 
	return 0; 
}