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;
}

作者：qingniaofy

补充：软件开发 , C++ ,