设为首页 加入收藏

TOP

PKU 2777 Count Color (线段树区间更新)
2015-07-24 05:50:34 来源: 作者: 【 】 浏览:4
Tags:PKU 2777 Count Color 线段 区间 更新


题意: 给你三个数:L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000),表示有一长度为L的板(1~L),

有T种颜色(1~T),然后有O个操作,初始板1~L的颜色为1,"C A B C"表示在区间A,B图上C颜色, "P A B" 表示询问

A,B区间有几种不同的颜色。



#include 
  
     
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 100000 #define LL long long using namespace std; struct Tree { int l,r,c;//c代表颜色,若区间(l,r)的颜色不止一种则c=-1; }tree[M*3]; int color[35];//在查询时,若[A,B]区间内出现过某种颜色k,则color[k]=true; void build(int id,int l,int r) { tree[id].l=l; tree[id].r=r; tree[id].c=1;//初始颜色为1 if(l==r) return ; build(id*2,l,(l+r)/2); build(id*2+1,(l+r)/2+1,r); } void update(int id,int l,int r,int co) { if(tree[id].l>=l&&tree[id].r<=r)//(l,r)完全覆盖id节点 { tree[id].c=co; return; } if(tree[id].c>0)//一直wa在这里 { tree[id*2].c=tree[id*2+1].c=tree[id].c; tree[id].c=-1; } tree[id].c=-1;//没有完全覆盖 int mid=(tree[id].l+tree[id].r)/2; if(mid>=r) update(2*id,l,r,co); else if(mid
       
        0) { color[tree[id].c]=true; return; } if(tree[id].l==tree[id].r) return; int mid=(tree[id].l+tree[id].r)/2; if(mid>=r) P(id*2,l,r); else if(mid
        
         b) swap(a,b); update(1,a,b,c); } else { scanf("%d%d",&a,&b); if(a>b) swap(a,b); memset(color,false,sizeof(color)); P(1,a,b); printf("%d\n",Ans(t)); } } return 0; } 
        
       
      
     
    
   
  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇ajax――dom基础 下一篇HDU 3360 National Treasures 奇..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: