A2464 色板游戏

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

// 线段树：每个结点存区间里出现过的颜色集合（T <= 30，用一个 32 位掩码表示）。
// 涂色是区间赋值，查询是区间按位或后数 1 的个数。

const int MAXL = 100000 + 5;

unsigned int maskv[4 * MAXL];
int lazy[4 * MAXL]; // 0 表示没有待下传的赋值

void apply(int p, int l, int r, int c) {
    maskv[p] = (c == 0) ? 0u : (1u << (c - 1));
    lazy[p] = c;
}

void push(int p, int l, int r) {
    if (lazy[p] == 0) return;
    int mid = (l + r) >> 1;
    apply(p << 1, l, mid, lazy[p]);
    apply(p << 1 | 1, mid + 1, r, lazy[p]);
    lazy[p] = 0;
}

void build(int p, int l, int r) {
    apply(p, l, r, 1); // 初始全部是 1 号色
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

void update(int p, int l, int r, int ql, int qr, int c) {
    if (ql <= l && r <= qr) {
        apply(p, l, r, c);
        return;
    }
    push(p, l, r);
    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);
    maskv[p] = maskv[p << 1] | maskv[p << 1 | 1];
}

unsigned int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return maskv[p];
    push(p, l, r);
    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);
    for (int i = 0; i < O; i++) {
        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;
}