HDU 1828 Picture（矩形周長並）

HDU 1828 Picture

題目鏈接

題意：給定n個矩形，輸出矩形周長並

思路：利用線段樹去維護，分別從4個方向掃一次，每次多一段的時候，就查詢該段未被覆蓋的區間長度，然後周長就加上這個長度，4個方向都加完就是答案

代碼：

#include 
#include 
#include 
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;
}