学步园

                                                           Mars Maps

Time Limit:1000MSMemory Limit:30000KB
Total Submit:17Accepted:8

Description

  In the year 2051, several Mars expeditions have explored different areas of the red planet and produced maps of these areas. Now, the BaSA (Baltic Space Agency) has an ambitious plan: they would like to produce a map of the whole planet. In order to calculate
the necessary effort, they need to know the total size of the area for which maps already exist. It is your task to write a program that calculates this area.

Write a program that:
reads the description of map shapes,
computes the total area covered by the maps,
writes the result.

Input

The inputstarts with a line containing a single integer N (1<=N<=10 000), the number of available maps. Each of the following N lines describes a map. Each of these lines contains four integers x1, y1, x2 and y2 (0<=x1<x2<=30 000, 0<=y1<y2<=30 000). The values
(x1,y1) and (x2,y2) are the coordinates of, respectively, the bottom-left and the top-right corner of the mapped area. Each map has rectangular shape, and its sides are parallel to the x- and y-axis of the coordinate system.

Output

  The output should contain one integer A, the total explored area (i.e. the area of the union of all rectangles).  

Sample Input

  2
10 10 20 20
15 15 25 30

Sample Output

225

Source

BOI2001

http://acm.cs.ecnu.edu.cn/problem.php?problemid=1467

lrj书上的线段树例题，先把坐标离散化，从左往右扫描矩形的竖线，把每一个竖线作为一个事件点，维护纵坐标上的线段树，左竖线就添加线段，右竖线就删除线段，再用线段树的覆盖范围乘以每两个事件点的横坐标距离，依次累加即为最终答案。

添加，删除的时间复杂度都为O（logn），所以最终的复杂度为O（n*logn）。

#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;

const int maxn=10000;

struct node{
	int st,end,c,m;             //线段树节点区间描述[st,end],覆盖层数c，区间长度m
	}Node[8*maxn];

struct line{
	int x,y1,y2;
	bool j;                    //每个矩形的左右竖线
	bool operator<(const line& o)const{
		return x<o.x;
		};
	}Line[2*maxn+5];

int y[2*maxn+5],ty[2*maxn+5];      //y[]记录纵坐标值，ty[]用于辅助数组y[]，使其不重复
map<int,int> indexs;

void init(int root,int st,int end){
	Node[root].st=st;  Node[root].end=end;
	Node[root].c=0;    Node[root].m=0;
	if(st-end>1){
		init(2*root,st,(st+end)/2);
		init(2*root+1,(st+end)/2,end);
		}
	}

void update(int root,int st,int end,int l,int r,bool j){
	if(r<=st||l>=end)return;
	if(l<=st&&r>=end){
		if(j)
			++Node[root].c;
		else
			--Node[root].c;
		}
	else{
		update(root*2,st,(st+end)/2,l,r,j);
		update(root*2+1,(st+end)/2,end,l,r,j);
		}
	if(Node[root].c>0)
		Node[root].m=y[end]-y[st];
	else
		Node[root].m=(end-st==1)?0:(Node[2*root].m+Node[2*root+1].m);
	}

int main(){
	int N;
	scanf("%d",&N);
	int x1,x2,y1,y2;
	for(int i=0;i<N;++i){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		Line[2*i].x=x1;Line[2*i].y1=y1;
		Line[2*i].y2=y2;Line[2*i].j=1;
		Line[2*i+1].x=x2;Line[2*i+1].y1=y1;
		Line[2*i+1].y2=y2;Line[2*i+1].j=0;
		ty[2*i]=y1;ty[2*i+1]=y2;
		}
	sort(Line,Line+2*N);
	sort(ty,ty+2*N);
	y[0]=ty[0];
	int cnt=0;
	indexs[y[0]]=0;
	for(int i=1;i<2*N;++i)
		if(ty[i]!=ty[i-1]){
			y[++cnt]=ty[i];
			indexs[y[cnt]]=cnt;
			}
	for(int i=0;i<2*N;++i){
		Line[i].y1=indexs[Line[i].y1];
		Line[i].y2=indexs[Line[i].y2];
			}
	init(1,0,cnt);
    update(1,0,cnt,Line[0].y1,Line[0].y2,Line[0].j);
	__int64 ans=0;
	for(int i=1;i<2*N;++i){
		ans+=Node[1].m*(Line[i].x-Line[i-1].x);
		update(1,0,cnt,Line[i].y1,Line[i].y2,Line[i].j);
		}
	cout<<ans<<endl;
	return 0;
	}