扫描线矩形周长的并 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 ;

 }