P1558 色板游戏

#include <bits/stdc++.h>
using namespace std;

const int MAXL = 100000 + 5;

// mask[p]：该结点区间内出现过的颜色集合（第 c-1 位代表颜色 c）
unsigned int mask[MAXL * 4];
// lazy[p]：整段赋值标记，0 表示没有待下传的标记
int lazy[MAXL * 4];

void build(int p, int l, int r) {
    mask[p] = 1u;   // 初始整块色板都是 1 号色
    lazy[p] = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

// 把整个结点区间涂成颜色 c
void apply(int p, int c) {
    mask[p] = 1u << (c - 1);
    lazy[p] = c;
}

void pushDown(int p) {
    if (lazy[p]) {
        apply(p << 1, lazy[p]);
        apply(p << 1 | 1, lazy[p]);
        lazy[p] = 0;
    }
}

void update(int p, int l, int r, int ql, int qr, int c) {
    if (ql <= l && r <= qr) {
        apply(p, c);
        return;
    }
    pushDown(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr, c);
    if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, c);
    mask[p] = mask[p << 1] | mask[p << 1 | 1];
}

unsigned int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mask[p];
    pushDown(p);
    int mid = (l + r) >> 1;
    unsigned int res = 0;
    if (ql <= mid) res |= query(p << 1, l, mid, ql, qr);
    if (qr > mid) res |= query(p << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, T, O;
    cin >> L >> T >> O;

    build(1, 1, L);

    while (O--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (a > b) swap(a, b);
        if (op == 'C') {
            int c;
            cin >> c;
            update(1, 1, L, a, b, c);
        } else {
            unsigned int m = query(1, 1, L, a, b);
            cout << __builtin_popcount(m) << '\n';
        }
    }
    return 0;
}