C++ 数颜色（使用标准输入输出）

Question

描述

有 n 位小朋友排成一排，从左到右编号为 1-n。

每次老师会给一个区间 [l,r] 内的小朋友分发颜色为 c 的糖果，总共会分发 q 次 [l,r,c]。

在分发结束后，请你求出每位小朋友手中糖果的颜色种类数。

例如 n=5, q=3，第一次分发[1,4,1]之后：

1:{1}
2:{1}
3:{1}
4:{1}
5:{}
2:{1}
3:{1}
4:{1}
5:{}

第二次分发[2,5,2]：

1:{1}
2:{1,2}
3:{1,2}
4:{1,2}
5:{2}
2:{1,2}
3:{1,2}
4:{1,2}
5:{2}

第三次分发[4,5,1]：

1:{1}
2:{1,2}
3:{1,2}
4:{1,1,2}
5:{1,2}
2:{1,2}
3:{1,2}
4:{1,1,2}
5:{1,2}

 

最终每个人的颜色种类数为 [1,2,2,2,2]。

输入格式

第一行输入2个整数 n,q

接下来 q 行，每行3个整数 l,r,c 代表一次分发

输出格式

输出1行，包含 n 个整数代表最终每个人持有的颜色种类数量。

样例输入

5 3
1 4 1
2 5 2
4 5 1

样例输出

1 2 2 2 2

Answer 1

参考GPT和自己的思路：

对于这个问题，可以使用线段树并维护每一个区间内颜色的集合。具体实现如下：

首先定义一个结构体表示颜色的集合：

struct ColorSet {
    unordered_set<int> s;
    void insert(int x) { s.insert(x); }
    void insert(const ColorSet& t) { s.insert(t.s.begin(), t.s.end()); }
};

其中，ColorSet 维护了一个无序集合 s，表示集合内的所有颜色。可以实现 insert 函数用于插入新的颜色或另一个集合。

然后定义线段树的节点结构体，其中 sum 表示颜色的集合，color 表示颜色数量：

struct Node {
    ColorSet sum;
    int color;
};

接下来定义线段树的一些基本操作。首先是更新操作，可以直接将一个节点的 sum 表示为左右子节点的并集，再统计一下集合的大小即可：

void pushup(Node& u, const Node& l, const Node& r) {
    u.sum = l.sum;
    u.sum.insert(r.sum);
    u.color = u.sum.s.size();
}

然后是查询操作，直接返回节点 u 的颜色数量即可：

int query(Node& u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return u.color;
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += query(u_lson, ql, qr);
    if (qr > mid) res += query(u_rson, ql, qr);
    return res;
}

最后是单点修改操作，先判断是否是叶子节点，然后直接将颜色加入颜色集合中，再向上更新即可：

void modify(Node& u, int l, int r, int p, int x) {
    if (l == r) {
        u.sum.insert(x);
        u.color = u.sum.s.size();
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) modify(u_lson, p, x);
    else modify(u_rson, p, x);
    pushup(u, u_lson, u_rson);
}

完整的代码如下：