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

银河里的星星

落在人间

 
 
 

日志

 
 

线段树 poj 2777 count color  

2009-03-02 22:30:50|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

线段树就像树状数组一样,通过将一个长为n的段落,划分为O(logn)个子段落,这样就可以通过维护子段落的属性,来求得整个段落的属性。可以证明,任何一个子段在一颗线段树上不会被划分为超过2logn个子段。

一个典型的线段树如下:


线段树的实现可以采用数组静态实现,就像二叉堆一样,每个节点则维护了一个子段的相关属性。也可以采用动态实现,即采用动态内存分配。线段树的关键在找到什么属性来用线段树维护,为了维护这个属性,每个节点该包含那些信息。而在这样的结构下如何完成插入,删除和查询。


count color来自http://acm.pku.edu.cn/JudgeOnline/problem?id=2777

在考虑其实现时,很明显的应该将 color作为一个属性,但是该问题,由于存在一个更新问题,而且更新的时候是一个段而不是某个点,这样导致与普通的实现不同。如何在O(logn)时间内完成C 操作,成为关键。另一方面,由于该颜色数目小于30,因此可以考虑采用int的位表示颜色几何,因为这样可以方便的利用位并求合集。


而在更新时,如果我们考虑保证所有的节点都正确地代表的段内的颜色的集合,这样将导致所需的更新操作远远增加,以如下[1,8]为例,我们要更新它,则涉及到其所有父亲,以及其所有孩子,极端情况下就会需要O(n)个子段要更新。所以这样更新不现实,另一方面,考虑线段树,是否可以只更新那些组成该线段的子段呢?


如果仅更新子段,而仍然按照普通的查询是不可以的,因为我们无法保证查询时候比如区间为[1,4],我们更新[1,2],如果进行染色时,我们只更新[1,2]这个节点,而不更新其子节点,而当我们查询[2,3]时,需要[2]这个点,如果我们还是按照原来的查询方法,即把[2,3]分成[2][3],实际上就会得到那个未被更新的节点[2]的颜色了,这样就是不行的了。

但是我们只要稍加变化,即在查询某个段时,如果发现它是某个段的子段,而该段只有一个颜色,那么我们就可以终止不必往下进行了。比如上面的[2,3]我们在线段树上分裂到了[1,2]发现[2]包含在[1,2]并且[1,2]是单色的,那么我们就不必往下找了。如果这样查询,我们就可以在更新时只需更新那些子段,同时注意更新这些子段的父亲就可以了,不必再往下更新到所有的子节点了。

综上,我们实现时要注意两个事情,更新时,要进行必要的往下往上更新,其中往下更新指在节点为单色时,同时更新子结点的颜色,以防止该节点被染回原色。向上更新,指更新父节点的颜色,insert最后一句即是。参见红色代码部分。

而查询时要注意:一旦发现单色节点,则返回。红色代码部分


//数组静态实现

#include <cstdio>
#include<algorithm>
using namespace std;
#define MAX_N 300003
//segement tree
int seg[MAX_N];
int bin_exp[32];
void init(){
    for(int i = 0 ; i < 32 ; i++){
        bin_exp[i] = 1 << i;
    }
}
void build(int node,int begin,int end,int col){   
    seg[node] = col;
    if(begin == end){
        return;
    }
    build(2*node,begin,begin+(end-begin)/2,col);
    build(2*node+1,begin+(end-begin)/2+1,end,col);

}
bool is_single(int x){
    return (x&(x-1))== 0;
}
void insert(int node,int begin,int end,int left,int right,int col){
    if(left > end || right < begin) return;
    if(begin >= left && end <= right){seg[node] = col;return;}

//如果当前点颜色与要染的色相同,当然不必再染色
    if(seg[node] == col)return;

/*

注意这句的作用,是为了防止最后    seg[node] = seg[2*node] | seg[2*node+1];又把seg[node]的颜色还原,比如我们更新[1,2]时,如果[1,2]被调用了,而我们在更新时不对其子节点同时更新,那么最后 seg[node] = seg[2*node] | seg[2*node+1];就会把我们[1,2]的颜色染回原色。

*/
    if(is_single(seg[node])){
        seg[2*node] = seg[2*node+1] = seg[node];
    }
    insert(2*node,begin,begin+(end-begin)/2,left,right,col);
    insert(2*node+1,begin+(end-begin)/2+1,end,left,right,col);

//必须进行更新,这样才能保证父亲是对的,即如果我们对[1,2]染色了,必须同时更新它的那些父亲节点,即包含它的段。
    seg[node] = seg[2*node] | seg[2*node+1];
}
int color = 0;
void query(int node,int begin,int end,int left,int right){

   //如果当前区间与查询区间不相交,同时意味着后面的执行都是相交的那些段
    if(begin > right || end < left)return;
    if(begin >= left && end <= right){color |= seg[node];return;}

    //很明显,如果当前是单色的,则结果是显然的,不用再看了
    if(is_single(seg[node])){color |= seg[node];return;}
    query(2*node,begin,begin+(end-begin)/2,left,right);
    query(2*node+1,begin+(end-begin)/2+1,end,left,right);
}
 int cal(int n){
   int cnt=0;
   while(n>0){
     if(n%2) cnt++;
     n>>=1;
   }
   return cnt;
 }
int main(){
   int L,T,O;
   scanf("%d%d%d",&L,&T,&O);
   build(1,1,L,1);
   char cmd[10];
   int s,e,c;
   while(O--){
     scanf("%s",&cmd);
     if(cmd[0]=='C'){
       scanf("%d%d%d",&s,&e,&c);
       if(s>e) swap(s,e);
       insert(1,1,L,s,e,1<<(c-1));
     }
     else if(cmd[0]=='P'){
       color=0;
       scanf("%d%d",&s,&e);
       if(s>e) swap(s,e);
       query(1,1,L,s,e);
       printf("%d\n",cal(color));
     }
   }
    return 0;
}

//参考实现,动态版本

  #include<iostream>
  #include<algorithm>
  #include<cstdio>
  using namespace std;
  #define MAXN 100001
 
  struct Seg_Tree{
    Seg_Tree *leftptr,*rightptr;
    int left,right;
   int col;
 }*Root;

 int L,T,O,cnt;
 int nmem;
 Seg_Tree mem[MAXN*10];

 Seg_Tree* CreateNode(){
   Seg_Tree* p=&mem[nmem++];
   memset(p,0,sizeof(Seg_Tree));
   return p;
 }

 Seg_Tree* CreateTree(int s,int e){
   Seg_Tree* root=CreateNode();
   root->left=s;
   root->right=e;
   if(s!=e){
     int mid=(s+e)/2;
     root->leftptr=CreateTree(s,mid);
     root->rightptr=CreateTree(mid+1,e);
   }
   return root;
 }

 bool odd(int n){//判断奇偶的,其实就判断是不是只有一种颜色。
   return (n&(n-1))==0;
 }

 void UpdateTree(Seg_Tree* root,int s,int e,int c){
     //printf("update:(%d %d) ",root->left,root->right);
     if(s<=root->left&&e>=root->right){
       root->col=c;
       return;
     }
     if(root->col==c) return;
     if(odd(root->col)){
       root->leftptr->col=root->col;
       root->rightptr->col=root->col;
     }
     int mid=(root->left+root->right)/2;
     if(s<=mid) UpdateTree(root->leftptr,s,e,c);
     if(e>mid) UpdateTree(root->rightptr,s,e,c);
     root->col=root->leftptr->col|root->rightptr->col;
 }
 void Query(Seg_Tree* root,int s,int e,int &cnt){
     if(s<=root->left&&e>=root->right){
     //printf("query:(%d %d) ",root->left,root->right);
         cnt=cnt|root->col;
         return;
     }
     if(odd(root->col)){
         cnt=cnt|root->col;
         return;
     }
   int mid=(root->left+root->right)/2;
   if(s<=mid) Query(root->leftptr,s,e,cnt);
   if(e>mid) Query(root->rightptr,s,e,cnt);
 }
int color = 0;
void query(Seg_Tree* root,int s,int e){
    if(e < root->left || s > root->right)return;
    if(s == root->left && e == root->right) {
       // printf("found.%d",root->col);
        color= root->col;
        return;
    }
   int mid=(root->left+root->right)/2;
   if(s<=mid) query(root->leftptr,s,e);
   if(e>mid) query(root->rightptr,s,e);
}
//void printf
 int cal(int n){
   int cnt=0;
   while(n>0){
     if(n%2) cnt++;
     n>>=1;
   }
   return cnt;
 }
 int main(){
   nmem=0;
   scanf("%d%d%d",&L,&T,&O);
   Root=CreateTree(1,L);
   UpdateTree(Root,1,L,1);
   char cmd[10];
   int s,e,c;
   while(O--){
     scanf("%s",&cmd);
     if(cmd[0]=='C'){
       scanf("%d%d%d",&s,&e,&c);
       if(s>e) swap(s,e);
       UpdateTree(Root,s,e,1<<(c-1));
     }
     else if(cmd[0]=='P'){
       cnt=0;
       scanf("%d%d",&s,&e);
       if(s>e) swap(s,e);
       Query(Root,s,e,cnt);
       printf("%d\n",cal(cnt));
     }
     else{      
       color = 0;  
       scanf("%d%d",&s,&e);
       query(Root,s,e);
     }
   }
   return 0;
 }

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

历史上的今天

评论

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

页脚

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