【IOI1998】Picture（扫描线+线段树）

问题来源：IOI1998 D2T1

题意：就是在一个平面内给出n个矩形，叫你计算将这些矩形合并以后，新图形的周长。

例如：

上图是原本的矩形们　　　　　　---------->合并后的图形

解题思路：拿一条扫描线横着扫一次，遇到左边的边就在这条扫描线上+1，遇到右边的边就在这条扫描线上-1，在边被扫到的时候计算一下线上为0的个数即可。

　　因为如果只是单纯的For循环累加，时间会爆，所以我们采用线段树来存这条扫描线的状态优化效率即可。然后竖着再做同样的事做一遍。

　　时间效率应该是O（kn）(k是常数）。

附代码：

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<cmath>
 #define For(i,a,b) for (int i=a; i<=b; i++)
 #define Ford(i,a,b) for (int i=a; i>=b; i--)
 #define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
 #define mem(qaq,num) memset(qaq,num,sizeof(qaq));
 #define ll long long
 #define mod 1000000007
 #define INF 2000000000
 #define mid ((l+r)>>1)
 using namespace std;
 struct zxy{
     int mi,n,mark;
 }tr[];
 struct edge{
     int l,r,h,typ;
 }x[],y[];
 int n,ans,cnt;
 inline int in(){
     int x=,f=;
     char ch=getchar();
     while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
     while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
     return x*f;
 }
 inline void combine(int k){
     if (tr[k<<].mi==tr[k<<|].mi) tr[k].n=tr[k<<].n+tr[k<<|].n,tr[k].mi=tr[k<<].mi;
     else
         if(tr[k<<].mi<tr[k<<|].mi) tr[k].n=tr[k<<].n,tr[k].mi=tr[k<<].mi;
         else tr[k].n=tr[k<<|].n,tr[k].mi=tr[k<<|].mi;
     return;
 }
 inline void built(int l,int r,int k){
     if (l==r){
         tr[k].mi=;
         tr[k].n=;
         tr[k].mark=;
         return;
     }
     built(l,mid,k<<);
     built(mid+,r,k<<|);
     combine(k);
     tr[k].mark=;
 }
 inline void pushdown(int k){
     int ad=tr[k].mark;
     tr[k<<].mark+=ad;
     tr[k<<|].mark+=ad;
     tr[k<<].mi+=ad;
     tr[k<<|].mi+=ad;
     tr[k].mark=;
     return;
 }
 inline void update(int l,int r,int a,int b,int k,int ad){
     if (l>=a&&b>=r){
         tr[k].mark+=ad;
         tr[k].mi+=ad;
         return;
     }
     if (tr[k].mark) pushdown(k);
     if (a<=mid) update(l,mid,a,b,k<<,ad);
     if (b>mid) update(mid+,r,a,b,k<<|,ad);
     combine(k);
     return;
 }
 inline int query(int l,int r,int k,int a,int b){
     if (l==a&&r==b){
         if (tr[k].mi) return ;
         return tr[k].n;
     }
     if (tr[k].mark) pushdown(k);
     if (b<=mid) return query(l,mid,k<<,a,b);
     if (a>mid) return query(mid+,r,k<<|,a,b);
     return query(l,mid,k<<,a,mid)+query(mid+,r,k<<|,mid+,b);
 }
 void init(){
     n=in();
     For(i,,n){
         int x1=in()+,y1=in()+,x2=in()+,y2=in()+;
         x[++cnt].l=x1+,x[cnt].r=x2,x[cnt].h=y1,x[cnt].typ=;
         y[cnt].l=y1+,y[cnt].r=y2,y[cnt].h=x1,y[cnt].typ=;
         x[++cnt].l=x1+,x[cnt].r=x2,x[cnt].h=y2,x[cnt].typ=;
         y[cnt].l=y1+,y[cnt].r=y2,y[cnt].h=x2,y[cnt].typ=;
     }
     return;
 }
 bool cmp(edge a,edge b){
     return a.h<b.h||(a.h==b.h&&a.typ<b.typ);
 }
 void work(){
     sort(x+,x+cnt+,cmp);
     built(,,);
     For(i,,cnt)
         if (!x[i].typ){
             ans+=query(,,,x[i].l,x[i].r);
             update(,,x[i].l,x[i].r,,);
         }
         else{
             update(,,x[i].l,x[i].r,,-);
             ans+=query(,,,x[i].l,x[i].r);
         }
     sort(y+,y+cnt+,cmp);
     built(,,);
     For(i,,cnt)
         if (!y[i].typ){
             ans+=query(,,,y[i].l,y[i].r);
             update(,,y[i].l,y[i].r,,);
         }
         else{
             update(,,y[i].l,y[i].r,,-);
             ans+=query(,,,y[i].l,y[i].r);
         }
     return;
 }
 int main(){
     init();
     work();
     printf("%d",ans);
 }

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[e-mail].