登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

poj1177 picture  

2009-03-21 09:40:53|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

近来忙着挑战杯的项目,还有异构编程的,没有多少时间来做题,不过偶尔也会把题目记在心里,走路吃饭睡觉的时候那么想想。有时候也会有了一些新的看法和思考,感觉这样的思考方式倒是挺安静也挺深刻的,不会拘泥于做题中对数量的追求。

还是说说线段树吧,经典题目矩形并的周长,这个问题涉及的内容还比较多,包括排序,离散化,sweep line,还有线段树。

下面是一些问题,总体思路有了,细节上遇到的一些bug

1.线段树占用的空间大小?
为何分配了3*20000的大小,却在建立一个build(1,0,20000);的大小时内存访问溢出了?

void build(int node,int begin,int end){
    printf("%d %d %d\n",begin,end,node);
    seg_nodes[node].set_init();
    if(begin+1 == end){
        return;
    }
    build(2*node,begin,begin+(end-begin)/2);
    build(2*node+1,begin+(end-begin)/2,end);   
}
注意如果要用数组保存,则要关注线段树的深度,当20000的时候,其深度可以达到与32768同样的深度
纠正:将大小seg_nodes修改成4*20000

2.insert,dele失败
原因
    if(l <= begin && end <= r){
        seg_nodes[node].count++;
        update(node,begin,end);
        return ;
    }
语句忘记return;

3.我认为沿x轴方向和y轴方向的周长的计算方法是相同的。可是为何最终计算结果是错误的?
原因i++位置放错,而将x轴方向和y轴方向的周长等同处理的方法是正确的。
unsigned int sweep_line(segment array[],int size,int begin,int end){  
   unsigned long  area = 0;
   build(1,begin,end);
   int current,prev;
   current = prev = array[0].pos;
   for(int i = 0 ; i < size ; ){
      current = array[i].pos;
      area += (current - prev)*seg_nodes[1].c;     
      while(i < size && array[i].pos == current){    
            i++; 
            if(array[i].lor == 0){
                insert(1,begin,end,array[i].x,array[i].y);       
            }else{
                dele(1,begin,end,array[i].x,array[i].y);       
            }
      //i++ should be here. 
      }
      prev = current;

   }
   return area;
}

 

再附上完整的代码:

#include <iostream>
#include <cstdio>
#define MAX_N 20000*4
#define debug
#undef debug
struct node_t{
    int count;
    int c;
    bool lic;
    bool ric;
    void set_init(){
        count = 0;
        c = 0;
        lic = false;
        ric = false;
    }
} seg_nodes[MAX_N];
int num = 0;
void build(int node,int begin,int end){
    num++;
    //printf("%d %d %d\n",begin,end,node);
    seg_nodes[node].set_init();
    if(begin+1 < end){
        build(2*node,begin,begin+(end-begin)/2);
        build(2*node+1,begin+(end-begin)/2,end);   
    }
}
void update(int node,int begin,int end){
    //如果是叶子节点
    if(begin+1 == end){
        if(seg_nodes[node].count == 0){
            seg_nodes[node].lic = false;   
            seg_nodes[node].ric = false; 
            seg_nodes[node].c = 0; 
        }
        else{
            seg_nodes[node].lic = true;   
            seg_nodes[node].ric = true; 
            seg_nodes[node].c = 1; 
        }
    }
    //如果是内部节点
    else{
        if(seg_nodes[node].count == 0){
            seg_nodes[node].lic = seg_nodes[2*node].lic;   
            seg_nodes[node].ric = seg_nodes[2*node+1].ric;            
            seg_nodes[node].c =  seg_nodes[2*node].c + seg_nodes[2*node+1].c;
            if(seg_nodes[2*node].ric == true && seg_nodes[2*node+1].lic == true)
                     seg_nodes[node].c--;  
        }
        else{
            seg_nodes[node].lic = true;   
            seg_nodes[node].ric = true;  
            seg_nodes[node].c = 1; 
        }
    }
   

}
void insert(int node,int begin,int end,int l,int r){
    if(l <= begin && end <= r){
        seg_nodes[node].count++;
        update(node,begin,end);
        return ;
    }
    int mid = begin+(end-begin)/2;
    if(l < mid) insert(2*node,begin,mid,l,r);
    if(r > mid) insert(2*node+1,mid,end,l,r);
    update(node,begin,end);

}
void dele(int node,int begin,int end,int l,int r){
    if(l <= begin && end <= r){
        seg_nodes[node].count--;
        update(node,begin,end);
        return;
    }
    int mid = begin+(end-begin)/2;
    if(l < mid) dele(2*node,begin,mid,l,r);
    if(r > mid) dele(2*node+1,mid,end,l,r);
    update(node,begin,end);

}
struct segment{
    int pos;
    int lor;
    int x;
    int y;
    segment(){
        pos = lor = x = y = 0;
    }
    segment(int p,int l,int xx,int yy){
        pos = p;
        lor = l;
        x = xx;
        y = yy;
    }
}segs[2][5001*2];

void quick_sort(segment array[],int begin,int end){
    if(begin < end){
        int i,j;
        for(i = j = begin; i < end ; i++){
           if(array[i].pos < array[end].pos){
               segment temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               j++;      
           }    
        }
        segment temp = array[end];
        array[end] = array[j];
        array[j] = temp;
        quick_sort(array,begin,j-1);
        quick_sort(array,j+1,end);
    }

}
unsigned int sweep_line(segment array[],int size,int begin,int end){  
   unsigned long  area = 0;
   build(1,begin,end);
   int current,prev;
   current = prev = array[0].pos;
   for(int i = 0 ; i < size ; ){
      current = array[i].pos;
      area += (current - prev)*seg_nodes[1].c;     
      while(i < size && array[i].pos == current){
            if(array[i].lor == 0){
                insert(1,begin,end,array[i].x,array[i].y);       
            }else{
                dele(1,begin,end,array[i].x,array[i].y);       
            }
            i++;
      }
      prev = current;

   }
   return area;
}
void printf_seg(segment array[],int size){
    printf("seg:\n");
    for(int i = 0 ; i < size ; i++){
        printf("%d(%d,%d) ",array[i].pos-10000,array[i].x-10000,array[i].y-10000);
    }
    printf("\n");
}
void test_insert_dele(int begin,int end){
  
   build(1,begin,end);
   printf("%d",num);
   insert(1,begin,end,1,3);
   insert(1,begin,end,4,5);
   insert(1,begin,end,3,4);
   dele(1,begin,end,4,5);
   printf("seg:%d",seg_nodes[1].c);

}
int main()
{
   //test_insert_dele(0,20000);
   int n;
   int index_x = 0;
   int index_y = 0;
   unsigned long length = 0;
   scanf("%d",&n);
   for(int i = 0 ; i < n ; i++){
      int llx,lly,urx,ury;
      scanf("%d%d%d%d",&llx,&lly,&urx,&ury);
      llx += 10000;
      lly += 10000;
      urx += 10000;
      ury += 10000;
      //x轴方向的下线段
      segs[0][index_x++] = segment(lly,0,llx,urx);
      //x轴方向的上线段
      segs[0][index_x++] = segment(ury,1,llx,urx);
      //y轴方向的左线段
      segs[1][index_y++] = segment(llx,0,lly,ury);
      //y轴方向的右线段
      segs[1][index_y++] = segment(urx,1,lly,ury);
   }  
   //线段排序  
   quick_sort(segs[0],0,index_x-1);
   //printf_seg(segs[0],index_x);
   quick_sort(segs[1],0,index_y-1);
   //printf_seg(segs[1],index_y);
   //建立线段树
   //
   length += sweep_line(segs[0],index_x,0,20000);
   //printf("%d\n",length*2);
   length += sweep_line(segs[1],index_y,0,20000);
   printf("%d\n",length*2);
    return 0;
}

  评论这张
 
阅读(1772)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018