题意分析

1. 初始状态：长度为$L$的木板，所有段颜色为$1$。
2. 操作类型：
   • 染色操作（$C$）：将区间$[A, B]$染成颜色$C$，需处理$A > B$的情况（即交换$A, B$）。
   • 查询操作（$P$）：统计区间$[A, B]$内不同颜色的数量。
3. 关键约束：颜色总数$T \leq 30$，可用位压缩优化状态存储。

解题思路

1. 线段树设计：
   • 每个节点存储区间颜色的位掩码（$T$位二进制数，第$i$位为$1$表示存在颜色$i$）。
   • 合并子节点时，通过按位或操作合并颜色集合。
2. 懒标记：记录区间染色操作的待更新颜色，优化区间修改性能。
3. 查询处理：统计区间颜色掩码中$1$的位数（使用__builtin_popcount）。

实现步骤

1. 初始化：建树时所有节点颜色掩码为$1$（初始颜色）。
2. 区间染色（$C$操作）：
   • 若$A > B$，交换$A, B$。
   • 更新线段树区间$[A, B]$的掩码为$1 << (C-1)$，并下传懒标记。
3. 区间查询（$P$操作）：
   • 查询区间$[A, B]$的掩码，计算其中$1$的个数。
4. 边界处理：操作前检查$A, B$是否越界（$1 \leq A, B \leq L$）。

复杂度分析

• 时间：每次操作$O(\log L)$，总复杂度$O(O \log L)$。
• 空间：线段树开$4L$节点，$O(L)$。

代码实现

#include<cstdio>
#include<cstring>
#define lc ((rt)<<1)
#define rc ((rt)<<1|1)
#define maxn 100010

int ans[50];

struct node{
    int l,r,color;
}tree[maxn*4];

void build(int rt,int l,int r){//创建线段树 
    tree[rt].l=l; tree[rt].r=r;
	if(rt!=1) tree[rt].color=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid); build(rc,mid+1,r);
}

void lift_up(int rt){//颜色统一 
    if(tree[lc].color==tree[rc].color)
		tree[rt].color=tree[lc].color;
}

void push_down(int rt){//颜色下传 
    if(tree[rt].color){
        tree[lc].color=tree[rc].color=tree[rt].color;
        tree[rt].color=0;
    }
}

void modify(int rt,int l,int r,int c){//修改 
    if (tree[rt].l==l&&tree[rt].r==r){
        tree[rt].color=c;
        return;
    }
    push_down(rt);
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(r<=mid) modify(lc,l,r,c);
    else if(l>mid) modify(rc,l,r,c);
	else {modify(lc,l,mid,c);modify(rc,mid+1,r,c);}
    lift_up(rt);
}

void query(int rt,int l,int r){//查询 
    if(tree[rt].color){
        ans[tree[rt].color]=true;
        return;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;;
    if(r<=mid) query(lc,l,r);
    else if(l>mid) query(rc,l,r);
    else {query(lc,l,mid);query(rc,mid+1,r);}
}

int main(){
	
    int n,t,o;
    scanf("%d%d%d",&n,&t,&o);
	
    tree[1].color=1;
    build(1,1,n);
    for(int i=0;i<o;i++){
        char ch;
        scanf("\n%c",&ch);
        int l,r;
        if(ch=='C'){
            int c;
            scanf("%d%d%d",&l,&r,&c);
            modify(1,l,r,c);
        }
        else{
            memset(ans,0,sizeof(ans));
            scanf("%d%d",&l,&r);
            query(1,l,r);
            int tot=0;
            for(int k=1;k<=t;k++)
				if(ans[k])
					tot++;
            printf("%d\n",tot);
        }
    }
	
    return 0;
}