POJ2777 Count Color 线段树区间更新 - c++编程基础

TOP

POJ2777 Count Color 线段树区间更新

2015-07-24 05:47:34 来源: 作者: 【大中小】浏览:4次

题目描述：
长度为L个单位的画板，有T种不同的颜料，现要求按序做O个操作，操作分两种：
1.“C A B C”,即将A到B之间的区域涂上颜色C
2.“P A B”，查询[A，B]区域内出现的颜色种类

出现操作2时，请输出答案

PS:初始状态下画板颜色为1

一开始没有想那么好，用int整型位移来代替颜色，还是使用了最传统的bool color[来记录，可是不知道错在了哪里，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; const int N = 100000 + 5; typedef struct Node { int color; int l,r; }; Node tree[N * 4]; bool vis[50]; void init() { memset(vis,false,sizeof(vis)); } void build(int l,int r,int id) { tree[id].color = 1; tree[id].l = l; tree[id].r = r; if(tree[id].l == tree[id].r)return; int mid = (l + r)/2; build(l,mid,id<<1); build(mid + 1,r,id<<1|1); } void update(int l,int r,int id,int color) { if(tree[id].l >= l && tree[id].r <= r) { tree[id].color = color;return; } int mid = (tree[id].l + tree[id].r)/2; tree[id].color = -1; if(r <= mid) update(l,r,id<<1,color); else { if(l > mid)update(l,r,id<<1|1,color); else { update(l,mid,id<<1,color); update(mid+1,r,id<<1|1,color); } } } void update2(int l,int r,int id) { if(tree[id].color > 0) { vis[tree[id].color] = true;return; } if(tree[id].l == tree[id].r)return; int mid = (tree[id].l + tree[id].r)/2; if(r <= mid) update2(l,r,id<<1); else { if(l > mid)update2(l,r,id<<1|1); else { update2(l,mid,id<<1); update2(mid+1,r,id<<1|1); } } } int find(int x) { int ans = 0; for(int i=1;i<=x;i++) if(vis[i]) ans++; return ans; } int main() { int n,m,q; while(scanf("%d %d %d",&n,&m,&q) == 3 ){ memset(tree,0,sizeof(tree)); init(); build(1,n,1); while(q--) { char s[2]; scanf("%s",s); if(s[0] == 'C') { int x,y,c; scanf("%d %d %d",&x,&y,&c); if(x > y)swap(x,y); update(x,y,1,c); } else { int x,y; scanf("%d %d",&x,&y); init(); if(x > y)swap(x,y); update2(x,y,1); printf("%d\n",find(m)); } } } return 0; }

后来看了别人的一下，看到方法不一样，跑了案例也没发现自己的错误，继续检查还是不行，难道真的是方法不行？换了个方法过了，但是上面的代码错误原因还是没有查出来，WA哭

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; const int N = 100000 + 5; typedef struct Node { int l,r; int color; int flag; }; Node tree[N * 4]; void init() { memset(tree,0,sizeof(tree)); } void cal(int id) { tree[id].color = tree[id<<1].color | tree[id<<1|1].color; } void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].color = 1; tree[id].flag = 1; if(tree[id].l == tree[id].r) return; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void cover(int id) { tree[id<<1].color = tree[id].color; tree[id<<1].flag = 1; tree[id<<1|1].color = tree[id].color; tree[id<<1|1].flag = 1; tree[id].flag = 0; } void updata(int l,int r,int id,int col) { if(l <= tree[id].l && r >= tree[id].r) { tree[id].color = col; tree[id].flag = 1; return; } if(tree[id].color == col)return; if(tree[id].flag)cover(id); int mid = (tree[id].l + tree[id].r)/2; if(r <= mid) updata(l,r,id<<1,col); else if(l > mid)updata(l,r,id<<1|1,col); else { updata(l,mid,id<<1,col); updata(mid+1,r,id<<1|1,col); } cal(id); } int ans; void query(int l,int r,int id) { if(l <= tree[id].l && r >= tree[id].r) { ans |= tree[id].color;return; } if(tree[id].flag) { ans |= tree[id].color;return; } int mid = (tree[id].l + tree[id].r)/2; if(r <= mid) query(l,r,id<<1); else if(l > mid) query(l,r,id<<1|1); else { query(l,mid,id<<1); query(mid+1,r,id<<1|1); } } int main() { int n,m,q; while(scanf("%d %d %d",&n,&m,&q) == 3) { init(); build(1,n,1); char s[2]; while(q--) { scanf("%s",s); if(s[0] == 'C') { int x,y,c; scanf("%d %d %d",&x,&y,&c); if(x > y)swap(x,y); updata(x,y,1,1<<(c-1));//把颜色改成用正向委员算表示 } else { int x,y; scanf("%d %d",&x,&y); if(x > y)swap(x,y); ans = 0; query(x,y,1); int cnt = 0; while(ans) { if(ans%2)cnt++; ans /= 2; } printf("%d\n",cnt); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 11123 - Counting Trapizoid(..	下一篇：Linked List Cycle

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: