记录编号	83388	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2013-12-02 21:08:01	内存使用	2.19 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
using namespace std;
const int SIZEL=41001;
const int SIZEN=5001;
const int MINC=-10000,MAXC=10000;
class SEGMENT{
public:
	int left,right;
	int lchild,rchild;
	int len;//被覆盖长度
	int count;//被覆盖次数
};
class ORDER{//操作命令
public:
	bool type;//0是去掉1是加上
	int pos;//位置(如果是横线就意味着y坐标)
	int l,r;//区间
};
bool operator < (ORDER a,ORDER b){
	return a.pos<b.pos;
	return a.type>b.type;
}
#define now tree[root]
#define lson tree[now.lchild]
#define rson tree[now.rchild]
class SEGMENT_TREE{
public:
	SEGMENT tree[SIZEL];
	int tot;
	vector<ORDER> opt;//操作序列
	int cflen;//周界长度
	SEGMENT_TREE(){
		tot=0;
		cflen=0;
	}
	void build(int,int,int);
	void build(int,int);
	void update(int);
	void section_add(int,int,int,int);
	void section_add(int,int,int);
	int coverlen(void){//被覆盖的长度
		return tree[0].len;
	}
	int calc_cf(void);
}X,Y;//x是一系列横线,y是一系列竖线
void SEGMENT_TREE::build(int root,int l,int r){
	now.left=l,now.right=r;
	now.len=0;
	now.count=0;
	if(l<r){
		int mid=(l+r)>>1;
		now.lchild=++tot;
		build(tot,l,mid);
		now.rchild=++tot;
		build(tot,mid+1,r);
	}
	else{
		now.lchild=now.rchild=-1;
	}
}
void SEGMENT_TREE::build(int l,int r){
	build(tot,l,r);
}
void SEGMENT_TREE::update(int root){
	if(now.count) now.len=now.right-now.left+1;
	else{
		if(now.lchild!=-1) now.len=lson.len+rson.len;
		else now.len=0;
	}
}
void SEGMENT_TREE::section_add(int root,int l,int r,int t){
	if(root==-1) return;
	if(now.right<l||now.left>r) return;
	if(now.left>=l&&now.right<=r) now.count+=t;
	else{
		section_add(now.lchild,l,r,t);
		section_add(now.rchild,l,r,t);
	}
	update(root);
}
void SEGMENT_TREE::section_add(int l,int r,int t){
	section_add(0,l,r,t);
}
int SEGMENT_TREE::calc_cf(void){
	int i;
	int ll=0,nl;
	int sum=0;
	for(i=0;i<opt.size();i++){
		int t;
		t=opt[i].type?1:-1;
		section_add(opt[i].l,opt[i].r,t);
		if(i==opt.size()-1||opt[i].pos!=opt[i+1].pos||opt[i].type!=opt[i+1].type){
			nl=coverlen();
			sum+=abs(nl-ll);
			ll=nl;
		}
	}
	return sum;
}
class RECT{
public:
	int x1,x2,y1,y2;//1是小2是大
	void input(void){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		//x2--,y2--;
	}
};
void init(void){
	X.build(MINC,MAXC);
	Y.build(MINC,MAXC);
	RECT rec[SIZEN];
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) rec[i].input();
	ORDER temp;
	for(i=1;i<=n;i++){
		temp.type=1;
		temp.pos=rec[i].y1;
		temp.l=rec[i].x1,temp.r=rec[i].x2-1;
		X.opt.push_back(temp);
		temp.type=0;
		temp.pos=rec[i].y2;
		X.opt.push_back(temp);
	}
	sort(X.opt.begin(),X.opt.end());
	for(i=1;i<=n;i++){
		temp.type=1;
		temp.pos=rec[i].x1;
		temp.l=rec[i].y1,temp.r=rec[i].y2-1;
		Y.opt.push_back(temp);
		temp.type=0;
		temp.pos=rec[i].x2;
		Y.opt.push_back(temp);
	}
	sort(Y.opt.begin(),Y.opt.end());
}
int main(){
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	init();
	printf("%d\n",X.calc_cf()+Y.calc_cf());
	return 0;
}