[Baltic2001]Mars Maps

Time Limit:5000MS  Memory Limit:65536K
Total Submit:19 Accepted:7
Case Time Limit:1000MS

Description

给出N个矩形,N<=10000.其坐标不超过10^9.求其面积并

Input

先给出一个数字N,代表有N个矩形.
接下来N行,每行四个数,代表矩形的坐标.

Output

输出面积并

Sample Input

2
10 10 20 20
15 15 25 30

Sample Output

225

Source

这是很经典的题目了。离散化之后用扫描线扫过去，用线段树维护当前与扫描线相交的矩形的长度并。就可以降维了。。
不过我悲剧了。数组开小了囧。。WA了好几次。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
int n;
int Y[maxn*2];
struct Event
{
int x,l,r,d;
Event(){}
Event(int _x,int _l,int _r,int _d):x(_x),l(_l),r(_r),d(_d){}
bool operator<(const Event&o)const
{
return x<o.x;
}
}E[maxn*2];
void Init()
{
scanf("%d",&n);
int x[2],y[2],cnt=0;
rep(i,n)
{
rep(j,2)scanf("%d %d",x+j,y+j),Y[cnt++]=y[j];
E[2*i]=Event(x[0],y[0],y[1],1);
E[2*i+1]=Event(x[1],y[0],y[1],-1);
}
}
int Cover[8*maxn]={0},Sum[8*maxn]={0};
void change(int t,int l,int r,int a,int b,int d)
{
if(a>=r||b<=l) return;
if(a<=l&&b>=r)Cover[t]+=d;
else change(t*2,l,(l+r)/2,a,b,d),change(t*2+1,(l+r)/2,r,a,b,d);
if(Cover[t]>0)
Sum[t]=Y[r]-Y[l];
else
Sum[t]=(l+1==r)?0:(Sum[t*2]+Sum[t*2+1]);
}
void Work()
{
n<<=1;
sort(Y,Y+n);
rep(i,n)
{
E[i].l=lower_bound(Y,Y+n,E[i].l)-Y;
E[i].r=lower_bound(Y,Y+n,E[i].r)-Y;
}
sort(E,E+n);int last=E[0].x;long long Ans=0;
rep(i,n)
{
Event now=E[i];
if(now.x!=last)
{
Ans+=(long long)(Sum[1])*(now.x-last);
last=now.x;
}
change(1,0,n-1,now.l,now.r,now.d);
}
cout<<Ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}