F. Multi-Colored Segments - 题解

比赛与标签

比赛: Codeforces Round 826 (Div. 3) 标签: binary search, data structures, math, sortings 难度: *2000

题目大意喵~

主人，你好呀！(ฅ'ω'ฅ) 这道题是这样的：我们有 n 条彩色的线段，每一条都有自己的左端点 l、右端点 r 和颜色 c。

对于每一条线段，我们都想知道，离它最近的、并且颜色和它不一样的线段有多远。

两条线段之间的距离，是它们之间最短的距离。如果它们有重叠的部分，那距离就是 0 啦！如果它们不重叠，距离就是它们之间的空隙长度。

我们的任务就是，对给出的 n 条线段，分别计算出这个最短距离，然后一口气输出 n 个答案，喵~

解题思路喵！

拿到这个问题，最朴素的想法就是对每条线段，都去和其他所有颜色不同的线段比一比，找出最短的距离。但这样是 O(N^2) 的，N 有 2 * 10^5 这么大，肯定会超时的说！所以我们需要更聪明的办法，喵~

这题的关键在于“距离”的定义。对于一条线段 s = [l, r]，我们要找另一条不同色的线段 s' = [l', r']。

1. 如果 s' 在 s 的左边（r' < l），距离是 l - r'。为了让距离最小，我们希望 r' 尽可能大。
2. 如果 s' 在 s 的右边（l' > r），距离是 l' - r。为了让距离最小，我们希望 l' 尽可能小。
3. 如果它们有交集（比如 l <= r' 或者 l' <= r），距离就是 0。

这启发我们使用扫描线的思想！我们可以把所有线段的端点看作是数轴上的一系列事件。将所有线段按照左端点 l 从小到大排序，然后依次处理。

但是，只从左往右扫一遍是不够的。因为当我们处理线段 s 时，我们只能看到已经处理过的、l 比 s.l 小的线段，这只能帮我们处理情况 1。对于情况 2（寻找右边的线段），我们就无能为力了。

所以，一个绝妙的技巧就诞生了：做两次扫描！

第一次扫描：从左到右，寻找左边的最近邻居

我们先把所有线段按照左端点 l 从小到大排序。然后，我们从头到尾遍历这个排好序的线段数组。

在处理当前线段 s 时，我们需要在所有已经处理过的、颜色与 s 不同的线段中，找到那个右端点 r' 最大的。这样 s.l - r' 就会最小。

为了高效地做到这一点，我们可以用两个神器：

• std::map<int, int> max_r_per_color：一个映射，key 是颜色，value 是这种颜色目前出现过的线段里最大的右端点 r。
• std::multiset<int> all_max_r：一个多重集合，存放了 max_r_per_color 中所有的 value 值。multiset 可以自动排序，并且能让我们快速地找到最大值 (*rbegin())。

当处理线段 s 时：

1. 我们从 all_max_r 中找到当前全局最大的右端点 best_r。
2. 最关键的一步！ 这个 best_r 可能来自一条和 s 同色的线段。我们不能用它！所以要检查一下：如果 max_r_per_color[s.c] 恰好等于 best_r，并且 all_max_r 中 best_r 的数量只有 1（说明没有其他颜色也达到这个最大值），那我们就不能用它，而应该取 all_max_r 中第二大的值。
3. 找到合适的 best_r（来自不同颜色的线段）后，计算距离 max(0LL, s.l - best_r)，并用它来更新 s 的答案。
4. 处理完 s 后，我们要用 s 的信息去更新我们的两个神器，以便后续线段使用。我们更新 max_r_per_color[s.c] 和 all_max_r。

第二次扫描：从右到左，寻找右边的最近邻居

第一次扫描只解决了和左边线段的距离。现在我们来解决和右边线段的距离。

我们可以再次利用排好序的线段数组，这次从后往前遍历。逻辑是完全对称的！

在处理当前线段 s 时，我们需要在所有将要处理的（也就是 l 更大的）不同色线段中，找到那个左端点 l' 最小的。这样 l' - s.r 就会最小。

我们同样使用两个神器，不过这次是：

• std::map<int, int> min_l_per_color：记录每种颜色出现过的最小左端点 l。
• std::multiset<int> all_min_l：存放所有 min_l_per_color 的 value。

逻辑和第一次扫描非常相似，只是把找“最大右端点”换成了找“最小左端点”。

两次扫描结束后，对于每条线段，我们都分别计算了它与左边和右边最近的不同色线段的距离，取其中的较小值，就是最终的答案啦！如果中途有重叠的情况，距离自然就是 0 了，这个算法也能正确处理，喵~

代码实现

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

// 定义一个很大的数作为答案的初始值
const long long INF_LL = 4e9; 
const int INF_COORD = 2e9 + 7;

// 用结构体来存放每条线段的信息，包括它的原始编号id
struct Segment {
    int l, r, c, id;
};

void solve() {
    int n;
    std::cin >> n;
    std::vector<Segment> segments(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> segments[i].l >> segments[i].r >> segments[i].c;
        segments[i].id = i; // 记录原始id，方便最后输出
    }

    // 答案数组，初始化为一个很大的值
    std::vector<long long> ans(n, INF_LL);
    
    // 复制一份线段数组用于排序，不破坏原始顺序
    std::vector<Segment> sorted_segments = segments;
    // 按照左端点l从小到大排序，如果l相同，则按右端点r排序
    std::sort(sorted_segments.begin(), sorted_segments.end(), [](const Segment& a, const Segment& b) {
        if (a.l != b.l) {
            return a.l < b.l;
        }
        return a.r < b.r;
    });

    // ============ 第一次扫描：从左到右 ============
    // 目的是为每个线段找到其左侧最近的不同色线段
    std::map<int, int> max_r_per_color; // 记录每种颜色遇到的最大右端点
    std::multiset<int> all_max_r;     // 记录所有颜色最大右端点的集合，方便快速查找全局最大值

    for (const auto& s : sorted_segments) {
        int best_r = -1; // 寻找左侧不同色线段的最大右端点
        if (!all_max_r.empty()) {
            best_r = *all_max_r.rbegin(); // 全局最大右端点
            
            // 检查这个最大值是否来自同色线段
            auto it = max_r_per_color.find(s.c);
            if (it != max_r_per_color.end()) {
                if (it->second == best_r) { // 如果是同色线段
                    // 并且只有这一个同色线段提供了这个最大值
                    if (all_max_r.count(best_r) == 1) { 
                        if (all_max_r.size() > 1) {
                            // 那么我们只能选择第二大的右端点
                            best_r = *std::next(all_max_r.rbegin());
                        } else {
                            // 如果没有其他线段了，就找不到合适的
                            best_r = -1;
                        }
                    }
                }
            }
        }
        
        // 如果找到了一个合适的右端点
        if (best_r != -1) {
            // 计算距离，如果s.l <= best_r，说明有重叠，距离为0
            long long dist = std::max(0LL, (long long)s.l - best_r);
            // 更新答案
            ans[s.id] = std::min(ans[s.id], dist);
        }
        
        // 用当前线段s的信息更新数据结构
        auto it = max_r_per_color.find(s.c);
        if (it != max_r_per_color.end()) { // 如果这个颜色之前出现过
            if (s.r > it->second) { // 如果当前线段的r更大
                all_max_r.erase(all_max_r.find(it->second)); // 移除旧的r
                it->second = s.r; // 更新map
                all_max_r.insert(s.r); // 插入新的r
            }
        } else { // 如果是新颜色
            max_r_per_color[s.c] = s.r;
            all_max_r.insert(s.r);
        }
    }

    // ============ 第二次扫描：从右到左 ============
    // 目的是为每个线段找到其右侧最近的不同色线段，逻辑与第一次对称
    std::map<int, int> min_l_per_color; // 记录每种颜色遇到的最小左端点
    std::multiset<int> all_min_l;     // 记录所有颜色最小左端点的集合
    
    // 从排好序的数组末尾开始遍历
    for (int i = n - 1; i >= 0; --i) {
        const auto& s = sorted_segments[i];
        
        int best_l = INF_COORD; // 寻找右侧不同色线段的最小左端点
        if (!all_min_l.empty()) {
            best_l = *all_min_l.begin(); // 全局最小左端点
            
            // 同样，检查这个最小值是否来自同色线段
            auto it = min_l_per_color.find(s.c);
            if (it != min_l_per_color.end()) {
                if (it->second == best_l) { // 如果是同色
                    if (all_min_l.count(best_l) == 1) { // 且唯一
                        if (all_min_l.size() > 1) {
                            // 取第二小的值
                            best_l = *std::next(all_min_l.begin());
                        } else {
                            best_l = INF_COORD;
                        }
                    }
                }
            }
        }
        
        // 如果找到了合适的左端点
        if (best_l != INF_COORD) {
            // 计算距离，如果best_l <= s.r，说明有重叠，距离为0
            long long dist = std::max(0LL, (long long)best_l - s.r);
            // 更新答案
            ans[s.id] = std::min(ans[s.id], dist);
        }
        
        // 用当前线段s的信息更新数据结构
        auto it = min_l_per_color.find(s.c);
        if (it != min_l_per_color.end()) {
            if (s.l < it->second) {
                all_min_l.erase(all_min_l.find(it->second));
                it->second = s.l;
                all_min_l.insert(s.l);
            }
        } else {
            min_l_per_color[s.c] = s.l;
            all_min_l.insert(s.l);
        }
    }
    
    // 按原始顺序输出答案
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，对付大数据必备喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(N log N) 的说。 最耗时的部分是排序，需要 O(N log N)。两次扫描线的过程，每次都遍历 N 个线段。在循环内部，对 map 和 multiset 的操作（如 find, insert, erase）的复杂度是 O(log K)，其中 K 是不同颜色的数量（K <= N）。所以两次扫描的总时间是 O(N log K)。因此，总的时间复杂度由排序主导，为 O(N log N)，完全可以通过！

• 空间复杂度: O(N) 的说。 我们用了 segments 数组、sorted_segments 数组和 ans 数组，都是 O(N) 的空间。map 和 multiset 最多存储 K 个元素，K 不会超过 N，所以它们也是 O(N) 的空间。总的空间复杂度就是 O(N) 啦。

知识点与总结

这道题真是一次有趣的冒险呐！它完美地展示了扫描线算法的威力。

1. 核心思想: 将几何问题或区间问题通过排序，转化为一维的序列问题来处理，这就是扫描线的精髓！
2. 双向扫描: 对于需要同时考虑“左边”和“右边”影响的问题，采用一次正向扫描 + 一次反向扫描的技巧非常有效。它把一个复杂的问题拆分成了两个镜像的、更简单的问题。
3. 数据结构的选择: map 和 multiset 的组合在这里是点睛之笔！map 负责按类别（颜色）维护信息，而 multiset 负责维护全局信息并支持快速查询最值。特别是 multiset 能处理重复元素，并且能方便地找到第二大/第二小值，是解决本题“排除同色”这一关键点的利器。

希望这篇题解能帮助到你，主人！遇到问题不要怕，动动脑筋，总能找到像猫咪一样优雅的解决方法的！加油喵~ (๑•̀ㅂ•́)و✧