关于Kattis Path Crossing问题的理解与算法求解困惑

关于a_i的说明 #

• 相同的a_i代表不同玩家的路径位于同一竖直线上（x坐标相同）。每个玩家对应一条垂直于x轴的线段，格式为(a_i, b_i)到(a_i, c_i)，a_i是这条线段的x坐标。多个玩家可以拥有相同的a_i，也就是他们的路径是同一竖直线上的不同线段，而非同一玩家的重复记录。

关于b_i升序排列的含义 #

• 题目要求将所有玩家按b_i的数值从小到大排序，这里的b_i是每个玩家路径的其中一个端点的y坐标（另一个端点是c_i）。排序后，我们可以通过维护当前活跃的路径区间，高效判断后续路径是否与之前的路径产生交叉。

核心解题思路提示 #

• 两条路径交叉的判定条件：
  • 若两条路径的a_i不同（竖直线平行）：它们的y区间（取min(b,c)到max(b,c)的闭区间）存在重叠，即一条线段的y区间与另一条的y区间有交集（包括端点重合）。
  • 若两条路径的a_i相同（竖直线重合）：只要它们的y区间存在重叠，就视为交叉。
• 排序后可采用区间维护+计数的方式：遍历排序后的玩家，对每个玩家的y区间，统计与当前所有不同a_i的活跃区间的重叠次数，同时更新活跃区间（移除被当前区间完全包含的旧区间，或合并同a_i的重叠区间）。

内容的提问来源于stack exchange，提问作者judith