原题链接

题解1,种30棵树,每棵树代表每种颜色,树的每个节点代表这个颜色在对应区间上是否存在

code

#include<bits/stdc++.h>
using namespace std;
int st[32][400005]={0};
int lazy[32][400005]={0};

void pushdown(int who,int node)
{
    st[who][node*2]=lazy[who][node];
    lazy[who][node*2]=lazy[who][node];
    st[who][node*2+1]=lazy[who][node];
    lazy[who][node*2+1]=lazy[who][node];
    lazy[who][node]=-1;
}

void tuse(int node,int start,int end,int l,int r,int who,int val)
{
    if(start>r||end<l)return;

    if(start>=l&&end<=r)
    {
        st[who][node]=val;
        lazy[who][node]=val;
        return;
    }

    if(lazy[who][node]!=-1) pushdown(who,node);

    int mid=(start+end)/2;
    tuse(2*node,start,mid,l,r,who,val);
    tuse(2*node+1,mid+1,end,l,r,who,val);
    st[who][node]=st[who][node*2]||st[who][node*2+1];
}

int query(int node,int start,int end,int l,int r,int who)
{
    if(start>r||end<l)return 0;
    if(start>=l&&end<=r) return st[who][node];

    if(lazy[who][node]!=-1) pushdown(who,node);

    int mid=(start+end)/2;
    return query(node*2,start,mid,l,r,who)|query(node*2+1,mid+1,end,l,r,who);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l,t,o;
    cin>>l>>t>>o;
    for(int i=1;i<=4*(l+1);i++) st[1][i]=1;
    memset(lazy,-1,sizeof lazy);
    while(o--)
    {
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(y<x)swap(x,y);
        if(op=='C')
        {
            int k;
            cin>>k;
            for(int i=1;i<=t;i++)
            {
                if(k!=i)tuse(1,1,l,x,y,i,0);
                else tuse(1,1,l,x,y,i,1);
            }
        }
        else
        {
            int ans=0;
            for(int i=1;i<=t;i++) if(query(1,1,l,x,y,i)) ans++;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

题解2:一棵树,树的每个节点用二进制表示,01代表对应二进制位的颜色是否在这个区间上存在

code

#include<bits/stdc++.h>
using namespace std;
int st[400005]={0};
int lazy[400005]={0};
int a[35]={0,1};
void pushdown(int node)
{
    st[node]=lazy[node];//lazy代表该节点应该修改的值
    lazy[node*2]=lazy[node];
    lazy[node*2+1]=lazy[node];
    lazy[node]=0;
}

void tuse(int node,int start,int end,int l,int r,int val)
{
    if(lazy[node])  pushdown(node);

    if(start>r||end<l)  return;

    if(start>=l&&end<=r)
    {
        st[node]=a[val];//涂色后,其子节点附加延迟效果
        lazy[node*2]=a[val];
        lazy[node*2+1]=a[val];
        return;
    }

    int mid=(start+end)/2;
    tuse(2*node,start,mid,l,r,val);
    tuse(2*node+1,mid+1,end,l,r,val);
    st[node]=st[node*2]|st[node*2+1];//由于其区间被部分修改,所以需要重新计算,而若存在其子节点的延迟修改,那么这个点也早已被计算过了
}

int query(int node,int start,int end,int l,int r)
{
    if(lazy[node]) pushdown(node);//要修改也只是修改延迟效果的值

    if(start>r||end<l) return 0;

    if(start>=l&&end<=r) return st[node];

    int mid=(start+end)/2;
    return query(node*2,start,mid,l,r)|query(node*2+1,mid+1,end,l,r);//查询的是对应区间上的值,而不应修改非该区间的值
}

int finds(int now)
{
    int ans=0;
    while(now)
    {
        if(now&1)ans++;
        now>>=1;
    }
    return ans;
}
int main()
{
    for(int i=2;i<=30;i++)a[i]=a[i-1]<<1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l,t,o;
    cin>>l>>t>>o;
    for(int i=1;i<=4*l;i++) st[i]=1;
    while(o--)
    {
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(y<x)swap(x,y);
        if(op=='C')
        {
            int k;
            cin>>k;
            tuse(1,1,l,x,y,k);
        }
        else cout<<finds(query(1,1,l,x,y))<<endl;
    }
    return 0;
}