[线段树成段更新]poj 2777

题意：

??????? 一段区间从1-n的初始颜色为1，每次进行两种操作1，C a b c 把[a,b]这个区间染成颜色c。2，P a b查询[a,b]区间内有多少种颜色。

?

思路：

????? 这一题的关键在于用二进制存储一个区间内的颜色数量，新增颜色时对当前区间进行或操作来实现。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100000;
struct {
    int l , r , clo , num;
}node[nMax*3];
void build(int l ,int r ,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].clo = 1;
    node[u].num = 1;
    if(l == r){
        return;
    }
    int m = (l + r)>> 1;
    build(l , m , u*2);
    build(m + 1, r , u*2+1);
}

void update(int left ,int right ,int p ,int u){
//    cout<<left <<" tt "<<right<<" "<<u<<endl;
    if ( p == node[u].clo )return;
    if(left == node[u].l && right == node[u].r){
        node[u].clo = p;
        node[u].num = 1<<(p-1);
        return;
    }
    if(node[u].clo != 0){
        node[2*u].clo = node[u].clo;
        node[2*u].num = node[u].num;
        node[2*u+1].clo = node[u].clo;
        node[2*u+1].num = node[u].num;
        node[u].clo = 0;
        node[u].num = 0;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(left <= m){
        update(left , min(right , m), p ,u*2);
    }
    if(right >= m+1){
        update(max(left , m + 1) ,right ,p ,u*2+1);
    }
    node[u].num |= (node[2*u].num);
    node[u].num |= (node[2*u+1].num);
}
int ans;
void query(int left ,int right ,int u){
    if(node[u].clo != 0){
//            cout<<u<<" dddd "<<node[u].num<<" "<<node[u].clo<<endl;
        ans |= node[u].num;
        return;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(right <= m){
        query(left , right , u*2);
        return;
    }
    if(left >= m+1){
        query(left ,right , u*2 +1);
        return ;
    }
    query(left , m , u*2);
    query(m+1 , right , u*2 + 1);
}

int gao(int a){
    int res = 0;
    while(a){
        if(a & 1)res++;
        a >>= 1;
    }
    return res;
}
int main(){
    int n ,k ,m ,i ,j , a, b ,c;
    char str[5];
    while( scanf("%d%d%d",&n,&k,&m)!=EOF){
        build(1 ,n ,1);
        while(m--){
            scanf("%s",str);
            if( str[0] == ‘C‘){
                scanf("%d%d%d",&a,&b,&c);
                update(a ,b ,c ,1);
            }else{
                scanf("%d%d",&a,&b);
                ans = 0;
                query(a ,b ,1);
//                cout<<ans<<endl;
                printf("%d\n",gao(ans));
            }
        }
    }
    return 0;
}

??

?

[线段树成段更新]poj 2777

原文：http://bbezxcy.iteye.com/blog/2161642