本文共 2419 字，大约阅读时间需要 8 分钟。
题目链接：
题目大意： 多组输入，每组给出两个整数n和n表示一个区间，依次向一面墙上染不同的色，问染色后墙上能看见几种颜色。题目分析：
这是一个经典的线段树染色问题。由于区间的值域较大，为了减少内存占用和提高效率，通常可以通过离散化（Discretization）将区间映射到较小的范围内。具体来说，可以将所有区间的左右端点收集起来，排序并去重，得到一个唯一的离散值域。这样可以将原来的连续区间映射到一个有限的离散点上，从而减少线段树的空间复杂度。在实际实现中，可以使用线段树来维护区间信息，每个节点记录区间的值以及是否被覆盖。通过线段树的分治特性，可以高效地进行区间更新和查询操作。最后，可以通过查询线段树中的被覆盖的最小值和最大值，确定最终的颜色覆盖情况。
具体细节见代码：
#include#include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; struct position { int l, r; }; struct node { int val; bool flag; }; void pushdown(int root, int l, int r) { if (a[root].flag) { a[root].flag = false; if (l < r) { a[root << 1].flag = true; a[root << 1 | 1].flag = true; a[root << 1].val = a[root].val; a[root << 1 | 1].val = a[root].val; } } } void build(int root, int l, int r) { a[root].flag = true; if (l == r) return; int mid = l + r > 1 ? l + (r - l) / 2 : l; build(root << 1, l, mid); build(root << 1 | 1, mid + 1, r); } void update(int root, int l, int r, int ql, int qr, int val) { if (l > qr || r < ql) return; if (ql <= r && l <= qr) { a[root].val = val; a[root].flag = true; return; } pushdown(root, l, r); int mid = l + r > 1 ? l + (r - l) / 2 : l; update(root << 1, l, mid, ql, qr, val); update(root << 1 | 1, mid + 1, r, ql, qr, val); } void query(int root, int l, int r, int ql, int qr) { if (l == r || a[root].flag) { if (a[root].val) { st.insert(a[root].val); } return; } pushdown(root, l, r); int mid = l + r > 1 ? l + (r - l) / 2 : l; query(root << 1, l, mid, ql, qr); query(root << 1 | 1, mid + 1, r, ql, qr); } int main() { int t = read(); while (t--) { vector vpos; set st; int n = read(); for (int i = 1; i <= n; ++i) { int l = read(); int r = read(); vpos.push_back(l); vpos.push_back(r); } sort(vpos.begin(), vpos.end()); int siz = vpos.size(); for (int i = 1; i < siz; ++i) { if (vpos[i] - vpos[i - 1] > 1) { vpos.push_back(vpos[i - 1] + 1); } } sort(vpos.begin(), vpos.end()); vpos.erase(unique(vpos.begin(), vpos.end()), vpos.end()); siz = vpos.size(); build(1, 1, siz); for (int i = 1; i <= n; ++i) { int pos_l = lower_bound(vpos.begin(), vpos.end(), pos[i].l) - vpos.begin() + 1; pos[i].l = pos_l; int pos_r = lower_bound(vpos.begin(), vpos.end(), pos[i].r) - vpos.begin() + 1; pos[i].r = pos_r; update(1, 1, siz, pos[i].l, pos[i].r, i); } query(1, 1, siz, 1, siz); printf("%zu\n", st.size()); } return 0; }
转载地址：http://tqrxz.baihongyu.com/