思路分析 题意简化 nnn 个城市排成一排，每个城市有 4 种颜色中的 2 种。城市 iii 到 jjj 可直达当且仅当它们有相同颜色的传送门，花费 ∣i−j∣|i - j|∣i−j∣。求 xxx 到 yyy 的最小花费。 关键观察 由三角不等式 ∣x−z∣+∣z−y∣≥∣x−y∣|x-z| + |z-y| \geq |x-y|∣x−z∣+∣z−y∣≥∣x−y∣，经过中转不可能比直达更近。所以： 1. x=yx = yx=y：答案为 000 2. xxx 和 yyy 有共同颜色：直达，答案为 ∣x−y∣|x - y|∣x−y∣ 3. xxx 和 yyy 无共同颜色：必须找一个中转城市 zzz，使 zzz 与 xxx 有共同颜色、zzz 与 yyy 也有共同颜色 中转分析（WLOG X<YX < YX<Y） 4 种颜色选 2 种共 (42)=6\binom{4}{2} = 6(24 )=6 种类型。若 xxx 和 yyy 无共同颜色，它们的颜色集恰好互补（各占 2 种，覆盖全部 4 种）。兼容的中转类型 = 除了 xxx 的类型和 yyy 的类型以外的 4 种。 中转城市 zzz 的位置分三种情况： zzz 的位置 花费 最优选择 x<z<yx < z < yx<z<y（中间） y−xy - xy−x（最优） 存在即可 z<xz < xz<x（左边） x+y−2zx + y - 2zx+y−2z zzz 尽量大（最靠近 xxx） z>yz > yz>y（右边） 2z−x−y2z - x - y2z−x−y zzz 尽量小（最靠近 yyy） 数据结构 对每种类型维护一个 set<int>，用 lower_bound 快速查找最近的兼容城市。 复杂度 每次查询最多查 4 种类型，每次 O(logn)O(log n)O(logn)，总计 O(qlogn)O(q log n)O(qlogn)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码 核心总结 > 4 种颜色选 2 种只有 6 种搭配，且互不相容的类型对恰好互补 → 只需一个中转城市。对每种兼容类型用 set + lower_bound 找最近位置，查询 O(logn)O(log n)O(logn)。