线段树例题题解

卫星覆盖（NOI1997）

题面：

SERCOI（Space-Earth Resource Cover-Observe lnstitute）是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以覆盖空间直角坐标系中一定大小的立方体空间，卫星处于该立方体的中心。其中（x,y,z）（x,y,z）为立方体的中心点坐标， rr 为此中心点到立方体各个面的距离（即 rr 为立方体高的一半）．立方体的各条边均平行于相应的坐标轴。我们可以用一个四元组 (x,y,z,r)(x,y,z,r) 描述一颗卫星的状态，它所能覆盖的空间体积。由于一颗卫星所能覆盖的空间体积是有限的，因此空间中可能有若干颗卫星协同工作。它们所覆盖的空间区域可能有重叠的地方，如下图所示（阴影部分表示重叠的区域）。

写一个程序，根据给定的卫星分布情况，计算它们所覆盖的总体积。

思路

第一道自己做的NOI的题。

说白了就是求三维立方体的覆盖体积。

我们继承我们二维的思想，也就是用扫描线和线段树来求矩形的面积并。

扩展到三维上，也就是我们把他分割成很多高度为一的层，然后对于每一个层去做二维的面积并。

然后答案就是每一个层的二维面积并的和。

时间复杂度： $\Theta(n^2\log n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct owl{
	int x,y1,y2;
	int k;
	bool operator < (const owl & t)const{
		return x < t.x;
	}
}seg[N * 2];
struct hoot{
	int l,r;
	int cnt;
	int len;
}tr[N * 8];
vector<int>ys;
int find(int y){
	return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(int u){
	if (tr[u].cnt){
		tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
	}
	else if (tr[u].l != tr[u].r){
		tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
	}
	else{
		tr[u].len = 0;
	}
}
void build(int u,int l,int r){
	tr[u] = {l,r,0,0};
	if (l != r){
		int mid = l + r >> 1;
		build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
	}
}
void modify(int u,int l,int r,int k){
	if (tr[u].l >= l && tr[u].r <= r){
		tr[u].cnt += k;
		pushup(u);
	}
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid){
			modify(u << 1,l,r,k);
		}
		if (r > mid){
			modify(u << 1 | 1,l,r,k);
		}
		pushup(u);
	}
}
struct DID{
	int x,y,z,d;
}v[N];
struct SOREN{
	int x1,y1,x2,y2;
};
int main(){
	cin >> n;
	for (int i = 1; i <= n; i ++ ){
		cin >> v[i].x >> v[i].y >> v[i].z >> v[i].d;
	}
	int ans = 0;
	for (int Z = -1000; Z <= 1000; Z ++ ){
		ys.clear();
		int m = 0;
		vector<SOREN>vec;
		for (int i = 1; i <= n; i ++ ){
			int x1 = -3000, y1 = -3000, x2 = -3000, y2 = -3000;
			if (Z >= v[i].z - v[i].d + 1 && Z <= v[i].z + v[i].d){
				x1 = v[i].x - v[i].d,x2 = v[i].x + v[i].d;
				y1 = v[i].y - v[i].d,y2 = v[i].y + v[i].d;
			}
			if (x1 == -3000 && y1 == -3000 && x2 == -3000 && y2 == -3000){
				continue;
			}
			seg[m ++ ] = {x1, y1, y2, 1};
			seg[m ++ ] = {x2, y1, y2, -1};
			vec.push_back({x1,y1,x2,y2});
			ys.push_back(y1), ys.push_back(y2);
		}
		if (vec.size() == 1){
			ans += (vec[0].x2 - vec[0].x1) * (vec[0].y2 - vec[0].y1);
			continue;
		}
		if (m > 0){
			sort(ys.begin(), ys.end());
			ys.erase(unique(ys.begin(), ys.end()), ys.end());
			build(1, 0, ys.size() - 2);
			sort(seg, seg + m);
			int res = 0;
			for (int i = 0; i < m; i ++ ){
				if (i > 0){
					res += (tr[1].len) * (seg[i].x - seg[i - 1].x);
				}
				modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
			}
			ans += res;
		}
	}
	cout << ans;
	return 0; 
}