学步园

链接：点击打开链接

两种操作，C A B C是A到B中涂颜色C，P A B 是A到B区间有几种颜色。成段更新。需要注意的是这里没讲A一定大于B。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
struct node{
    int l;
    int r;
    int c;
    }anode[4*N];
int vis[33],ans;
void bulid(int l,int r,int n){
    anode[n].l=l;
    anode[n].r=r;
    anode[n].c=1;
    int mid=(l+r)>>1;
    if(l==r)
    return;
    bulid(l,mid,2*n);
    bulid(mid+1,r,2*n+1);
    }
void update(int l,int r,int n,int c){
    if(anode[n].l==l&&anode[n].r==r){
        anode[n].c=c;
        return;
        }
    if(anode[n].c>0){
        anode[2*n].c=anode[2*n+1].c=anode[n].c;
        anode[n].c=0;
        }
    int mid=(anode[n].l+anode[n].r)>>1;    
    if(r<=mid)
    update(l,r,2*n,c);
    else if(l>mid)
    update(l,r,2*n+1,c);
    else{
        update(l,mid,2*n,c);
        update(mid+1,r,2*n+1,c);
        }        
    }
void query(int l,int r,int n){
    if(anode[n].c!=0){
        if(!vis[anode[n].c]){
            ans++;
            vis[anode[n].c]=1;
            }
            return;
        }
    int mid=(anode[n].l+anode[n].r)>>1;    
    if(r<=mid)
    query(l,r,2*n);
    else if(l>mid)
    query(l,r,2*n+1);
    else{
        query(l,mid,2*n);
        query(mid+1,r,2*n+1);
        }        
    }            
int main(){
    int L,T,O,a,b,c;
    char str;
    while(~scanf("%d %d %d",&L,&T,&O)){
        bulid(1,L,1);
        while(O--){
            getchar();
            scanf("%c",&str);
            if(str=='C'){
                scanf("%d %d %d",&a,&b,&c);
                if(a>b)
                swap(a,b);
                update(a,b,1,c);
                }
            else{
                scanf("%d %d",&a,&b);
                if(a>b)
                swap(a,b);
                ans=0;
                memset(vis,0,sizeof(vis));
                query(a,b,1);
                printf("%d\n",ans);
                }    
            } 
        } 
        return 0;
    }