HDU 1828 Picture

题目链接

题意：给定n个矩形，输出矩形周长并

思路：利用线段树去维护，分别从4个方向扫一次，每次多一段的时候，就查询该段未被覆盖的区间长度，然后周长就加上这个长度，4个方向都加完就是答案

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 5005;

int n;

struct Rec {

	int x1, y1, x2, y2;

	void read() {

		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		x1 += 10000; y1 += 10000; x2 += 10000; y2 += 10000;

	}

} rec[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 cmp1(Line a, Line b) {

	if (a.y == b.y) return a.flag > b.flag;

	return a.y < b.y;

}

bool cmp2(Line a, Line b) {

	if (a.y == b.y) return a.flag > b.flag;

	return a.y > b.y;

}

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

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

struct Node {

	int l, r, add, addv, num;

	bool cover;

	void init(int l, int r) {

		this->l = l; this->r = r;

		add = addv = num = 0;

		cover = false;

	}

	void gao(int v) {

		addv += v;

		if (add == 0) num = r - l + 1;

		add += v;

		if (add == 0) num = 0;

	}

} node[4 * 20005];

void pushup(int x) {

	if (node[lson(x)].cover && node[rson(x)].cover && node[lson(x)].add == node[rson(x)].add) {

		node[x].cover = true;

		node[x].add = node[lson(x)].add;

	} else node[x].cover = false;

	node[x].num = node[lson(x)].num + node[rson(x)].num;

}

void pushdown(int x) {

	if (node[x].addv) {

		node[lson(x)].gao(node[x].addv);

		node[rson(x)].gao(node[x].addv);

		node[x].addv = 0;

	}

}

void build(int l, int r, int x = 0) {

	node[x].init(l, r);

	if (l == r) {

		node[x].cover = true;

		return;

	}

	int mid = (l + r) / 2;

	build(l, mid, lson(x));

	build(mid + 1, r, rson(x));

	pushup(x);

}

void add(int l, int r, int v, int x = 0) {

	if (node[x].cover && node[x].l >= l && node[x].r <= r) {

		node[x].gao(v);

		return;

	}

	int mid = (node[x].l + node[x].r) / 2;

	pushdown(x);

	if (l <= mid) add(l, r, v, lson(x));

	if (r > mid) add(l, r, v, rson(x));

	pushup(x);

}

int query(int l, int r, int x = 0) {

	if (node[x].cover && node[x].l >= l && node[x].r <= r)

		return node[x].num;

	int mid = (node[x].l + node[x].r) / 2;

	pushdown(x);

	int ans = 0;

	if (l <= mid) ans += query(l, r, lson(x));

	if (r > mid) ans += query(l, r, rson(x));

	pushup(x);

	return ans;

}

int solve() {

	build(0, 20000);

	int ans = 0;

	for (int i = 0; i < 2 * n; i++) {

		if (line[i].flag)

			ans += line[i].r - line[i].l - query(line[i].l, line[i].r - 1);

		add(line[i].l, line[i].r - 1, line[i].flag);

	}

	return ans;

}

int gao() {

	int ans = 0;

	for (int i = 0; i < n; i++) {

		line[i * 2] = Line(rec[i].x1, rec[i].x2, rec[i].y1, 1);

		line[i * 2 + 1] = Line(rec[i].x1, rec[i].x2, rec[i].y2, -1);

	}

	sort(line, line + 2 * n, cmp1);

	ans += solve();

	for (int i = 0; i < n; i++) {

		line[i * 2] = Line(rec[i].x1, rec[i].x2, rec[i].y2, 1);

		line[i * 2 + 1] = Line(rec[i].x1, rec[i].x2, rec[i].y1, -1);

	}

	sort(line, line + 2 * n, cmp2);

	ans += solve();

	return ans;

}

int main() {

	while (~scanf("%d", &n)) {

		for (int i = 0; i < n; i++)

			rec[i].read();

		int ans = 0;

		ans += gao();

		for (int i = 0; i < n; i++) {

			swap(rec[i].x1, rec[i].y1);

			swap(rec[i].x2, rec[i].y2);

		}

		ans += gao();

		printf("%d\n", ans);

	}

	return 0;

}