记录编号	277866	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	prefect1999	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2016-07-06 17:27:18	内存使用	0.64 MiB

/*
每个线段树维护cover和length两个域，分别表示当前结点对应区间被覆盖的层数以及被覆盖的长度（如果cover>1则length为当前区间长度）。
从上到下、从左到右各扫描一次，算出总的周长。
以从上到下为例：
将矩形拆成2条水平扫描线，下面的扫描线将cover值加1，上面的扫描线将cover值减1。将所有的扫描线从下到上排序，依次处理。
用当前的覆盖长度（即根节点的覆盖长度length[1]）减去上一次的覆盖长度的绝对值即为新增周长。
注意：若矩形两个点的横坐标分别为x1、x2，则对应的扫描线为[x1, x2-1]。 
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 21000;
const int delta = 10001;
int cover[maxn*4], length[maxn*4], y1, y2, v, n;
void maintain(int o, int L, int R)
{
	int lc = o * 2, rc = o * 2 + 1;
	if (cover[o])
	{
		length[o] = R - L + 1;
		return ;
	}
	if (R > L)
		length[o] = length[lc] + length[rc];
	else
		length[o] = 0;
}
void change(int o, int L, int R)
{
	if (y1 <= L && y2 >= R)
	{
		cover[o] += v;
	}
	else
	{
		int lc = o * 2, rc = o * 2 + 1;
		int M = L + (R - L) / 2;
		if (y1 <= M) change(lc, L, M);
		if (y2 > M) change(rc, M+1, R);
	}
	maintain(o, L, R);
}
void update(int L, int R, int V)
{
	y1 = L; y2 = R; v = V;
	change(1, 1, maxn);
}
struct Rect
{
	int x1, y1, x2, y2;
}rect[maxn];
struct Line
{
	int l, r, v, level;
	Line(){}
	Line(int L, int R, int V, int LEVEL) : l(L), r(R), v(V), level(LEVEL){}
	bool operator< (const Line &rhs) const
	{
		return level < rhs.level;
	}
}line[maxn];
int main()
{
	freopen("picture.in", "r", stdin);
	freopen("picture.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d %d %d", &rect[i].x1, &rect[i].y1, &rect[i].x2, &rect[i].y2);
		line[i*2] = Line(rect[i].x1, rect[i].x2, 1, rect[i].y1);
		line[i*2+1] = Line(rect[i].x1, rect[i].x2, -1, rect[i].y2);
	}
	sort(line, line + 2 * n);
	int last = 0, ans = 0;
	for (int i = 0; i < 2 * n; ++i)
	{
		update(line[i].l + delta, line[i].r + delta - 1, line[i].v);
		ans += abs(length[1] - last);
		last = length[1];
	}
	memset(cover, 0, sizeof(cover));
	memset(length, 0, sizeof(length));
	for (int i = 0; i < n; ++i)
	{
		line[i*2] = Line(rect[i].y1, rect[i].y2, 1, rect[i].x1);
		line[i*2+1] = Line(rect[i].y1, rect[i].y2, -1, rect[i].x2);
	}
	sort(line, line + 2 * n);
	last = 0;
	for (int i = 0; i < 2 * n; ++i)
	{
		update(line[i].l + delta, line[i].r + delta - 1, line[i].v);
		ans += abs(length[1] - last);
		last = length[1];
	}
	printf("%d\n", ans);	
	return 0;
}