POJ 2777 Count Color

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

2
1

有两种方法：一种是每次查询时都要统计对应区间延迟标记上颜色的种类，可以用set或简单哈希来实现。

一种是用二进制表示对应的区间涂了第几种颜色，这样每个区间除了延迟标记外，可以再开一个数组统计当前涂了哪几种颜色。这样就和一般的线段树一样了。

最后再统计一下1的数目。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long LL;
int sum[maxn<<2],col[maxn<<2],ll[maxn<<2],rr[maxn<<2];
inline void pushup(int i){
    sum[i]=sum[i<<1]|sum[i<<1|1];
}
inline void pushdown(int i){
    if(col[i]){
        col[i<<1]=col[i<<1|1]=col[i];
        sum[i<<1]=col[i];
        sum[i<<1|1]=col[i];
        col[i]=0;
    }
}
void build(int l,int r,int i){
    ll[i]=l;
    rr[i]=r;
    col[i]=1;
    if(l==r)return;
    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
    build(l,m,ls);
    build(m+1,r,rs);
    pushup(i);
}
void update(int l,int r,int v,int i){
    if(l<=ll[i]&&rr[i]<=r){
        col[i]=1<<(v-1);
        sum[i]=col[i];
        return ;
    }
    pushdown(i);
    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
    if(l<=m)update(l,r,v,ls);
    if(m<r)update(l,r,v,rs);
    pushup(i);
}
int query(int l,int r,int i){
    if(l<=ll[i]&&rr[i]<=r){
        return sum[i];
    }
    pushdown(i);
    int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
    int ans=0;
    if(l<=m)ans=ans|query(l,r,ls);
    if(m<r)ans=ans|query(l,r,rs);
    return ans;
}
int main()
{
    int l,t,o,a,b,c;
    char q[2];
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d%d",&l,&t,&o)){
        build(1,l,1);
        for(int i=0;i<o;i++){
            scanf("%s%d%d",q,&a,&b);
            if(a>b)swap(a,b);
            if(q[0]=='C'){
                scanf("%d",&c);
                update(a,b,c,1);
            }
            else {
                int res=query(a,b,1);
                int ans=0;
                while(res){
                    if(res&1)ans++;
                    res=res>>1;
                }
                printf("%d\n",ans);
            }
        }
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long LL;
int ll[maxn<<2],rr[maxn<<2],col[maxn<<2],vis[32];
int ans;
inline void pushdown(int i,int m){
    if(col[i]){
        col[i<<1]=col[i<<1|1]=col[i];
        col[i]=0;
    }
}
void build(int l,int r,int i){
   ll[i]=l;
   rr[i]=r;
   col[i]=1;
   if(l==r){
     return ;
   }
   int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
   build(l,m,ls);
   build(m+1,r,rs);
}
void update(int l,int r,int v,int i){
   if(l<=ll[i]&&rr[i]<=r){
    col[i]=v;
    return ;
   }
   pushdown(i,rr[i]-ll[i]+1);
   int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
   if(l<=m)update(l,r,v,ls);
   if(m<r) update(l,r,v,rs);
}
void query(int l,int r,int i){
   if(col[i]){
      if(!vis[col[i]]){
        ans++;
        vis[col[i]]=1;
      }
      return ;
   }
   pushdown(i,rr[i]-ll[i]+1);
   int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;
   if(l<=m)query(l,r,ls);
   if(m<r)query(l,r,rs);
}
int main()
{
    int l,t,o,a,b,c;
    char q[2];
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d%d",&l,&t,&o)){
        build(1,l,1);
        for(int i=0;i<o;i++){
            scanf("%s%d%d",q,&a,&b);
            if(a>b)swap(a,b);
            if(q[0]=='C'){
                scanf("%d",&c);
                update(a,b,c,1);
            }
            else {
                ans=0;
                memset(vis,0,sizeof vis);
                query(a,b,1);
                printf("%d\n",ans);
            }
        }
    }
}

POJ 2777 Count Color

原文：http://blog.csdn.net/u013497977/article/details/47059759