HDU 3642 Get The Treasury

题目链接

题意：给定一些立方体，求体积重叠超过3次的

思路：由于z坐标只有500，那么就可以枚举z坐标，每次做x，y的面积并即可，用线段树维护

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;
typedef long long ll;

int t, n;

struct Cube {
	int x1, y1, z1, x2, y2, z2;
	void read() {
		scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
	}
} cube[N];

struct Line {
	int l, r, y, flag;
	Line() {}
	Line(int l, int r, int y, int flag) {
		this->l = l; this->r = r;
		this->y = y; this->flag = flag;
	}
} line[N * 2];

bool cmp(Line a, Line b) {
	return a.y < b.y;
}

int hash[N * 2], ln, hn;

int find(int x) {
	return lower_bound(hash, hash + hn, x) - hash;
}

#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)

struct Node {
	int l, r, cover, len[4];
	void init(int l, int r) {
		this->l = l; this->r = r;
		cover = 0;
		memset(len, 0, sizeof(len));
	}
} node[N * 8];

void build(int l, int r, int x = 0) {
	node[x].init(l, r);
	node[x].len[0] = hash[r + 1] - hash[l];
	if (l == r) return;
	int mid = (l + r) / 2;
	build(l, mid, lson(x));
	build(mid + 1, r, rson(x));
}

void pushup(int x) {
	memset(node[x].len, 0, sizeof(node[x].len));
	if (node[x].l == node[x].r) {
		node[x].len[min(3, node[x].cover)] = hash[node[x].r + 1] - hash[node[x].l];
		return;
	}
	for (int i = 0; i <= 3; i++)
		node[x].len[min(3, node[x].cover + i)] += node[lson(x)].len[i] + node[rson(x)].len[i];
}

void add(int l, int r, int v, int x = 0) {
	if (node[x].l >= l && node[x].r <= r) {
		node[x].cover += v;
		pushup(x);
		return;
	}
	int mid = (node[x].l + node[x].r) / 2;
	if (l <= mid) add(l, r, v, lson(x));
	if (r > mid) add(l, r, v, rson(x));
	pushup(x);
}

ll solve(int z) {
	ln = hn = 0;
	for (int i = 0; i < n; i++) {
		if (cube[i].z1 <= z && cube[i].z2 > z) {
			line[ln++] = Line(cube[i].x1, cube[i].x2, cube[i].y1, 1);
			line[ln++] = Line(cube[i].x1, cube[i].x2, cube[i].y2, -1);
			hash[hn++] = cube[i].x1; hash[hn++] = cube[i].x2;
		}
	}
	sort(line, line + ln, cmp);
	sort(hash, hash + hn);
	int tmp = 1;
	for (int i = 0; i < hn; i++)
		if (hash[i] != hash[i - 1])
			hash[tmp++] = hash[i];
	hn = tmp;
	ll ans = 0;
	build(0, hn - 2);
	for (int i = 0; i < ln; i++) {
		if (i) ans += (ll)node[0].len[3] * (line[i].y - line[i - 1].y);
		add(find(line[i].l), find(line[i].r) - 1, line[i].flag);
	}
	return ans;
}

int main() {
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int Minz = INF, Maxz = -INF;
		for (int i = 0; i < n; i++) {
			cube[i].read();
			Minz = min(Minz, cube[i].z1);
			Maxz = max(Maxz, cube[i].z2);
		}
		ll ans = 0;
		for (int i = Minz; i < Maxz; i++)
			ans += solve(i);
		printf("Case %d: %lld\n", ++cas, ans);
	}
	return 0;
}

HDU 3642 Get The Treasury（线段树）