P1558 色板游戏¶

题目背景¶

阿宝上学了，今天老师拿来了一块很长的涂色板。

题目描述¶

色板长度为 \(L\)，\(L\) 是一个正整数，所以我们可以均匀地将它划分成 \(L\) 块 \(1\) 厘米长的小方格。并从左到右标记为 \(1, 2, \dots, L\)。

现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：

C A B C 指在 \(A\) 到 \(B\) 号方格中涂上颜色 \(C\)。
P A B 指老师的提问：\(A\) 到 \(B\) 号方格中有几种颜色。

学校的颜料盒中一共有 \(T\) 种颜料。为简便起见，我们把他们标记为 \(1, 2, \dots, T\)。开始时色板上原有的颜色就为 \(1\) 号色。面对如此复杂的问题，阿宝向你求助，你能帮助他吗？

输入格式¶

第一行有3个整数 \(L (1 \le L \le 10^5)\)，\(T (1 \le T \le 30)\) 和 \(O (1 \le O \le 10^5)\)。在这里 \(O\) 表示事件数。

接下来 \(O\) 行, 每行以 C A B C 或 P A B 的形式表示所要做的事情（这里 \(A, B, C\) 为整数, 可能 \(A> B\)，这样的话需要你交换 \(A\) 和 \(B\)）。

输出格式¶

对于老师的提问，做出相应的回答。每行一个整数。

输入输出样例 #1¶

输入 #1¶

输出 #1¶

2
1

题目分析¶

目的：对于老师的提问，进行相应的回答，统计出 \(A\) 到 \(B\) 号方格中有几种颜色。

由题目信息可知，核心动作有两个：

C A B C : 区间修改，将\([A,B]\)中的内容修改为 \(C\)。
P A B : 区间查询，统计\([A,B]\)中不同的数字个数。

整体来看的话是一个动态的序列问题，由此联想到线段树。

那么，关键问题就变成了如何利用线段树进行区间内不同元素个数的统计，以及进行区间整体修改这两个操作。

首先，考虑如何实现区间查询。观察到颜色的种类只有30个，数量较少，可以利用位运算来进行统计。可以让每种颜色分别对应上二进制中的一位，如1号颜色对应\(0000\cdots 0001\),2号颜色对应\(0000\cdots 0010\)，以此类推。这样的话，整体的区间颜色填涂情况就可以利用按位或进行合并，区间内不同颜色的数量就变成了二进制中1的总数了。

void pushup(int u){//合并结点u维护的区间颜色信息
  w[u]=w[2*u]|w[2*u+1];
}

之后，考虑如何进行区间整体颜色的修改。操作中的颜色修改是覆盖类型的修改，所以可以考虑直接进行赋值覆盖。另外需要注意的是，为了加速整体修改，往往加入延迟标记的技巧，在对标记值进行下方时，为了避免覆盖动作影响实际内容，当延迟标记为空时则不进行下放动作。

void maketag(int u,int L,int R,int val){
    lzy[u]=val;
    w[u]=val;
}
void pushdown(int u,int L,int R){
    if(lzy[u]==0) return ;//没有修改，则不进行操作
    int mid=(L+R)/2;
    maketag(2*u,L,mid,lzy[u]);
    maketag(2*u+1,mid+1,R,lzy[u]);
    lzy[u]=0;
}

代码实现¶

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5;
/*
颜色：1~30  -> 2^0 ~ 2^(29) 
涂色：对应位标记(覆盖涂色)
统计：统计二进制中1的个数  
*/
int n,T,m;
int w[N<<2],lzy[N<<2];
void maketag(int u,int L,int R,int val){
    lzy[u]=val;
    w[u]=val;
}
void pushdown(int u,int L,int R){
    if(lzy[u]==0) return ;//没有修改，则不进行操作
    int mid=(L+R)/2;
    maketag(2*u,L,mid,lzy[u]);
    maketag(2*u+1,mid+1,R,lzy[u]);
    lzy[u]=0;
}
void pushup(int u){
    w[u]=w[2*u]|w[2*u+1];
}
void build(int u,int L,int R){
    if(L==R){//原有的颜色为1号色
        w[u]=1;
        return ;
    }
    int mid=(L+R)/2;
    build(2*u,L,mid);
    build(2*u+1,mid+1,R);
    pushup(u);
}
bool inRange(int L,int R,int l,int r){
    return l<=L&&R<=r;
}
bool outofRange(int L,int R,int l,int r){
    return r<L||R<l;
}
int query(int u,int L,int R,int l,int r){
    //返回[l,r]的整体涂色状态
    if(inRange(L,R,l,r)){
        return w[u];
    }else if(!outofRange(L,R,l,r)){
        pushdown(u,L,R);
        int mid=(L+R)/2;
        return query(2*u,L,mid,l,r)|query(2*u+1,mid+1,R,l,r);
    }else{
        return 0;
    }
}
void update(int u,int L,int R,int l,int r,int col){

    if(inRange(L,R,l,r)){
        maketag(u,L,R,col);
        return ;
    }else if(!outofRange(L,R,l,r)){
        pushdown(u,L,R);
        int mid=(L+R)/2;
        update(2*u,L,mid,l,r,col);
        update(2*u+1,mid+1,R,l,r,col);
        pushup(u);
    }
}
int lowbit(int x){
    return x&-x;
}
int count(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)){
        ans++;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>T>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        char op;
        int a,b,c;
        cin>>op>>a>>b;
        if(a>b) swap(a,b);
        if(op=='C'){
            cin>>c;
            update(1,1,n,a,b,(1<<(c-1)));
        }else{
            cout<<count(query(1,1,n,a,b))<<"\n";
        }
    }
    return 0;
}