【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:13960948839@163.com.

巴特西

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

最新文章

热门文章