线段树

/*3514.   River Pollution
Accepted
2010 5 23
一道用线段树求矩形并的题目。
http://acm.tju.edu.cn/toj/showp.php?pid=3514
题目:受污染的河流会污染到它周围的村庄,给出河流的坐标求受污染的村庄的总数。
求矩形的并的方法:
将矩形的平行于y轴或者说平行于列的边,按照x从小到大排列。
然后求面积时,就分别求所到的边,与上一个边在y轴上覆盖了多长,用这个长度乘以
这两条边之间的x轴上的距离,搜索所有的边,就可以求的矩形并的面积。
在我们求在y轴上覆盖了多长的时候,可以用线段树来处理。当数据过大或不一定为整数时
还需要加上离散化。

ps:因为一小点错,错了一下午,刷了一片wrong answer。还好最后这个小问题还是被我给发现了。
坚持就是胜利啊。*/

 

 

#include<iostream>
#include
<algorithm>
#include
<cmath>
#include
<cstring>
using namespace std;

struct seg
{
       
int x,y1,y2;
       
int flag;
       seg()
{}
       seg(
int _x,int _y1,int _y2,int _f): x(_x),y1(_y1), y2(_y2), flag(_f){}
       
bool operator < ( const seg& a) const
       
{
            
return x < a.x;
       }

}
Edge[40005];
int f[600005];
int m[600005];
void update(int left,int right,int step)
{
    
if(left==right-1)
    
{
        
if(f[step]>0)
        m[step]
=1;
        
else
        m[step]
=0;
        
return ;
    }

     
if(f[step]>0)
     m[step]
=right-left;
     
else
     m[step]
=m[2*step]+m[step*2+1];
}


void Buildtree(int left,int right,int l,int r,int c,int step)
{
    
if(left==right-1)
    
{
        f[step]
+=c;
        update(left,right,step);
        
return ;
    }

    
if(left==l&&right==r)
     
{
          f[step]
+=c;
          update(left,right,step);
          
return ;
     }

     
else
     
{
         
int mid=(left+right)>>1;
         
if(r<=mid)
         Buildtree(left,mid,l,r,c,
2*step);
         
else if(l>=mid)
         Buildtree(mid,right,l,r,c,
2*step+1);
         
else
         
{
           Buildtree(left,mid,l,mid,c,
2*step);
           Buildtree(mid,right,mid,r,c,
2*step+1);
         }

         update(left,right,step);
         
return ;
     }

}


int main()
{
    
int t,n,x1,y1,x2,y2,i,j,my,pre;
    
long long ans;
    scanf(
"%d",&t);
    
while(t--)
    
{
            scanf(
"%d",&n);
            memset(f,
0,sizeof(f));
            memset(m,
0,sizeof(m));
            j
=my=0;
            
for(i=0;i<n;i++)
            
{
                 scanf(
"%d%d%d%d",&x1,&y1,&x2,&y2);
                 
if(x1==x2)
                 
{
                           
if(y1>y2) swap(y1,y2);
                           Edge[j
++]=seg(x1-1,y1,y2,1);
                           Edge[j
++]=seg(x1+1,y1,y2,-1);
                 }

                 
else if(y1==y2)
                 
{
                          
if(x1>x2) swap(x1,x2);
                          Edge[j
++]=seg(x1,y1-1,y1+1,1);
                          Edge[j
++]=seg(x2,y1-1,y1+1,-1);
                 }

                 my
=max(y2,my);
            }

            sort(Edge,Edge
+j);
            ans
=0;
            pre
=Edge[0].x;
            
for(i=0;i<j;i++)
            
{
                   ans
+=m[1]*(Edge[i].x-pre);
                   Buildtree(
0,my+2,Edge[i].y1,Edge[i].y2,Edge[i].flag,1);
                   pre
=Edge[i].x;
            }

              cout
<<ans<<endl;
    }

    
return 0;
}


posted on 2010-05-23 20:34 YUANZX 阅读(361) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年7月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜