扫描线矩形周长的并 POJ1177

//扫描线矩形周长的并 POJ1177
// 我是按x轴 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
// #include <memory.h>
// #include <bits/stdc++.h>
using namespace std;
#define LL long long
typedef pair<int,int> pii;
const LL inf = 0x3f3f3f3f;
const LL MOD =100000000LL;
const int N = ;
const double eps = 1e-;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;} struct node{
int x1,x2,y;
int flag;
bool operator < (const node &a) const{
return y<a.y||(y==a.y&&flag>a.flag);
}
}e[N<<]; int color[N<<];
int sum[N<<],hashh[N<<];
int cnt[N<<],pl[N<<],pr[N<<];
void pushup(int rt,int l,int r){
if(color[rt]) {
sum[rt]=hashh[r+]-hashh[l];
cnt[rt]=;
pl[rt]=pr[rt]=;
}
else if(l!=r) {
sum[rt]=sum[rt<<]+sum[rt<<|];
cnt[rt]=cnt[rt<<]+cnt[rt<<|]-(pr[rt<<]&&pl[rt<<|]);
pr[rt]=pr[rt<<|];
pl[rt]=pl[rt<<];
}
else sum[rt]=cnt[rt]=pl[rt]=pr[rt]=;
}
void update(int l,int r,int L,int R,int rt,int f){
if(l<=L&&R<=r){
color[rt]+=f;
pushup(rt,L,R);
return;
}
int mid=(L+R)>>;
if(l<=mid) update(l,r,L,mid,rt<<,f);
if(r>mid) update(l,r,mid+,R,rt<<|,f);
pushup(rt,L,R);
} int main(){
// fre();
int n;
scanf("%d",&n);
memset(color,,sizeof(color));
memset(sum,,sizeof(sum));
memset(cnt,,sizeof(cnt));
memset(pr,,sizeof(pr));
memset(pl,,sizeof(pl));
int x1,x2,y1,y2;
for(int i=;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
e[i*-].x1=e[i*].x1=x1;
e[i*-].x2=e[i*].x2=x2;
e[i*-].y=y1,e[i*].y=y2;
e[i*-].flag=,e[i*].flag=-;
hashh[i*-]=x1,hashh[i*]=x2;
}
sort(e+,e++*n);
sort(hashh+,hashh++*n);
int ans=;
int lastsum=;
e[].y=e[].y;
for(int i=;i<=*n;i++){
ans+=(e[i].y-e[i-].y)**cnt[];
int l=lower_bound(hashh+,hashh++*n,e[i].x1)-hashh;
int r=lower_bound(hashh+,hashh++*n,e[i].x2)-hashh-;
if(l<=r) update(l,r,,*n,,e[i].flag);
ans+=abs(sum[]-lastsum);
lastsum=sum[];
}
printf("%d\n",ans);
return ;
}