记录编号	234164	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2016-03-07 12:29:30	内存使用	2.73 MiB

#include<cstdio>
#include<algorithm>
#define lch(x) x<<1
#define rch(x) x<<1|1
using namespace std;
int ans=0;
int read(){
	char ch;int x;bool minus=false;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if(ch=='-'){
		ch=getchar();minus=true;
	}
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
	return minus?-x:x;
}
struct seg{
	int lx,rx;
	int y;	
	int tp;
	bool operator < (const seg&a)const{
		return y<a.y;
	}
}segs[20005];int size=1;
int ledge[20005];//某个区间是否有边界 
int redge[20005];
int sum[100000];//某个区间有几根竖直边界 
int times[100000];//某个坐标处在几个矩形内（包括边界）
void insert(int rt,int l,int r,int s,int tp){
//	printf("i(%d %d)",l,r);
	if(l==r){
		times[rt]+=tp;
	//	printf("time%dedge%d\n",times[rt],edge[l]);
		if(!times[rt]&&(ledge[l]^redge[l]))sum[rt]=1;
		else sum[rt]=0;
	}else{
		int mid=(l+r)>>1;
		if(s<=mid)insert(lch(rt),l,mid,s,tp);
		else insert(rch(rt),mid+1,r,s,tp);
		sum[rt]=sum[lch(rt)]+sum[rch(rt)];
	}
//	printf("%d ",sum[rt]);
}
struct Seg{
	int x;int uy,dy;
	int tp;
	bool operator<(const Seg &a)const{
		return x<a.x;
	}
}Segs[20005];int Size=1;
int dEdge[20005],uEdge[20005];
int Sum[100005];
int Times[100005];
void Insert(int rt,int l,int r,int s,int tp){
	if(l==r){
		Times[rt]+=tp;
		if(!Times[rt]&&(dEdge[l]^uEdge[l]))Sum[rt]=1;
		else Sum[rt]=0;
	}else{
		int mid=(l+r)>>1;
		if(s<=mid)Insert(lch(rt),l,mid,s,tp);
		else Insert(rch(rt),mid+1,r,s,tp);
		Sum[rt]=Sum[lch(rt)]+Sum[rch(rt)];
	}
} 
int main(){
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	int n=read();
	if(n==0)printf("0\n");
	else{
		int x1,y1,x2,y2;
		for(int i=1;i<=n;++i){
			x1=read()+10001;y1=read()+10001;
			x2=read()+10001;y2=read()+10001;
			segs[size].lx=x1;segs[size].rx=x2;segs[size].y=y1;segs[size].tp=1;
			size++;
			segs[size].lx=x1;segs[size].rx=x2;segs[size].y=y2;segs[size].tp=-1;
			size++;
			Segs[Size].dy=y1;Segs[Size].uy=y2;Segs[Size].x=x1;Segs[Size].tp=1;
			Size++;
			Segs[Size].dy=y1;Segs[Size].uy=y2;Segs[Size].x=x2;Segs[Size].tp=-1;
			Size++;
		}
		sort(segs+1,segs+size);
		sort(Segs+1,Segs+size);
		for(int i=1;i<size;++i){
	//		printf("y==%d\n",segs[i].y);
			ans+=sum[1]*(segs[i].y-segs[i-1].y);
			if(segs[i].tp==1){
				ledge[segs[i].lx]++;
				redge[segs[i].rx]++;
			}else{
				ledge[segs[i].lx]--;
				redge[segs[i].rx]--;
			}
			insert(1,1,20005,segs[i].lx,0);
			insert(1,1,20005,segs[i].rx,0);
			for(int k=segs[i].lx+1;k<segs[i].rx;++k)insert(1,1,20005,k,segs[i].tp);
		}
		for(int i=1;i<Size;++i){
			ans+=Sum[1]*(Segs[i].x-Segs[i-1].x);
			if(Segs[i].tp==1){
				uEdge[Segs[i].uy]++;
				dEdge[Segs[i].dy]++;
			}else{
				uEdge[Segs[i].uy]--;
				dEdge[Segs[i].dy]--;
			}
			Insert(1,1,20005,Segs[i].dy,0);
			Insert(1,1,20005,Segs[i].uy,0);
			for(int k=Segs[i].dy+1;k<Segs[i].uy;++k)Insert(1,1,20005,k,Segs[i].tp);
		}
		printf("%d\n",ans);
	}	
	fclose(stdin);fclose(stdout);
	return 0;
}