poj 2777

區間染色問題，線段樹
[cpp]
#include<iostream> 
#include<algorithm> 
using namespace std; 
 
#define lson u<<1 
#define rson u<<1|1 
#define MAXN 100010 
 
bool visit[55]; 
 
struct Node{ 
    int lef,rig,color; 
}T[MAXN<<2]; 
 
void Build(int u,int l,int r){ 
    T[u].lef=l;T[u].rig=r; 
    T[u].color=1;//一開始初始化為0，tle 了兩次 
    if(l==r)return; 
    int mid=(l+r)>>1; 
    Build(lson,l,mid);Build(rson,mid+1,r); 
} 
 
void PushDown(int u){ 
    if(T[u].color!=-1){ 
        T[lson].color=T[rson].color=T[u].color; 
        T[u].color=-1; 
    } 
} 
 
void Update(int u,int l,int r,int val){ 
    if(l<=T[u].lef&&T[u].rig<=r){T[u].color=val;return;} 
    else { 
        PushDown(u); 
        if(l<=T[lson].rig)Update(lson,l,r,val); 
        if(r>=T[rson].lef)Update(rson,l,r,val); 
    } 
} 
 
void Query(int u,int l,int r){ 
    if(T[u].color!=-1){//查詢到該區間有color就可以return了 
        visit[T[u].color]=true;return; 
    } 
    if(T[u].lef==T[u].rig)return; 
    PushDown(u); 
    if(l<=T[lson].rig)Query(lson,l,r); 
    if(r>=T[rson].lef)Query(rson,l,r); 
} 
 
int main(){ 
    int L,T,O; 
    char cmd; 
    int a,b,c; 
    while(scanf("%d%d%d",&L,&T,&O)==3){ 
        Build(1,1,L); 
        while(O--){ 
            scanf(" %c",&cmd); 
            if(cmd=='C'){ 
                scanf("%d%d%d",&a,&b,&c); 
                Update(1,a,b,c); 
            } 
            else {   
                scanf("%d%d",&a,&b); 
                memset(visit,false,sizeof(visit)); 
                Query(1,a,b); 
                int cnt=0; 
                for(int i=1;i<=50;i++)if(visit[i])cnt++; 
                printf("%d\n",cnt); 
            } 
        } 
    } 
    return 0; 
}