POJ 2777 Count Color

题目传送门

一、题目大意

一条很长（\(L\)）的画板，有\(T\)种颜色，\(O\)个操作；每次操作将一个区间刷成一种颜色，或者查询一个区间内所含的颜色数。

二、题目分析

经典的区间染色问题。
因为总共的颜色最多只有\(30\)种，因此我们可以用一个范围在\(int\)的二进制数\(bit\)存储每一种颜色（\(bit\)的二进制下的每一位代表着一种颜色）
之后我们只需要用线段树对区间上的\(bit\)进行维护即可。注意在我们区间合并\(pushup\)的过程中，我们需要将某个结点的左右儿子的值都或起来，作为该结点的值。
之后对于操作\(C\)，我们只需要将区间\([l,r]\)的值更新即可。
对于操作\(Q\)，我们只需要将区间\([l,r]\)的\(bit\)求出，并求出\(bit\)在二进制位下的\(1\)的个数为答案。

ps：这个问题种还有一个坑点，对于每一个操作种的\(l\)和\(r\)，题目中并没有说明哪个是左区间，哪个是有区间，因此我们还需要特判一下大小。

三、实现代码

// http://poj.org/problem?id=2777
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 100010;

struct Node {
    int l, r;
    int add, sum;
} tr[N << 2];

void pushup(int u) {
    tr[u].sum = tr[ls].sum | tr[rs].sum; //因为是模拟二进制的操作，所以采用 或 运算即可完成拼接操作
}
void pushdown(int u) {
    if (tr[u].add) {                         //如果lazy tag > 0,需要向后续子孙传递下去
        tr[ls].add = tr[rs].add = tr[u].add; //向左右儿子传递lazy tag
        tr[ls].sum = tr[rs].sum = tr[u].add; // TODO
        tr[u].add = 0;                       //清空lazy tag
    }
}
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].sum = 1; // sum记录的其实是一个30位的二进制压缩模拟数字，此时置为1表示最后一位即0位为1，是默认的颜色
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int v) {
    if (l <= tr[u].l && tr[u].r <= r) { //[l,r]包含了u的范围
        tr[u].add = 1 << (v - 1);
        tr[u].sum = 1 << (v - 1);
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;       //中间点
    pushdown(u);                              //下传lazy tag
    if (l <= mid) modify(u << 1, l, r, v);    //修改左儿子
    if (r > mid) modify(u << 1 | 1, l, r, v); //修改右儿子
    pushup(u);                                //因为左右儿子数据的变更，需要再次向上更新父节点信息
}

int query(int u, int l, int r) {
    // 1、省略后面复杂的左右区间判断，是一种写法的优化！！！
    if (l > tr[u].r || r < tr[u].l) return 0;
    // 2、区间内直接返回
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    // 3、左右各半
    pushdown(u); //下传lazy tag
    // 4、返回左右和
    return query(ls, l, r) | query(rs, l, r);

    // 下面这种yxc的写法out了，代码长，还不好记
    // int ans = 0;
    // int mid = tr[u].l + tr[u].r >> 1;
    // if (l <= mid) ans = query(u << 1, l, r);
    // if (r > mid) ans = ans | query(u << 1 | 1, l, r);
    // return ans;
}

int main() {
    int n, t, m; //区间[1,n],t种颜色,m个操作
    scanf("%d%d%d", &n, &t, &m);
    //构建线段树
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if (l > r) swap(l, r); //坑点题目没说哪个大哪个小，需要特判
        if (op[0] == 'C') {
            int v;
            scanf("%d", &v);
            modify(1, l, r, v);
        } else {
            int ans = query(1, l, r);
            int cnt = __builtin_popcount(ans); //获取某个数二进制位1的个数
            printf("%d\n", cnt);
        }
    }
    return 0;
}
poj线段树

相关

poj 2301（水题）

#直径，线段树#51nod 1766 树上的最远点对

poj2917

P2859 [USACO06FEB]Stall Reservations S POJ3190

POJ1002_487-3279_C++

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

poj 1064（注意最后的输出是r不是mid）

HDU 2457 POJ 3691 DNA repair（AC自动机+DP）

关于 线段树 的一些认识

背包问题 POJ1742 Coins

Cause: java.lang.ClassNotFoundException: Cannot find class: com.kuang.pojo.User

标签