T3-9 Colored Portals

思路分析

题意简化

$n$ 个城市排成一排，每个城市有 4 种颜色中的 2 种。城市 $i$ 到 $j$ 可直达当且仅当它们有相同颜色的传送门，花费 $|i - j|$。求 $x$ 到 $y$ 的最小花费。

关键观察

由三角不等式 $|x-z| + |z-y| \geq |x-y|$，经过中转不可能比直达更近。所以：

1. $x = y$：答案为 $0$
2. $x$ 和 $y$ 有共同颜色：直达，答案为 $|x - y|$
3. $x$ 和 $y$ 无共同颜色：必须找一个中转城市 $z$，使 $z$ 与 $x$ 有共同颜色、$z$ 与 $y$ 也有共同颜色

中转分析（WLOG $x < y$）

4 种颜色选 2 种共 $\binom{4}{2} = 6$ 种类型。若 $x$ 和 $y$ 无共同颜色，它们的颜色集恰好互补（各占 2 种，覆盖全部 4 种）。兼容的中转类型 = 除了 $x$ 的类型和 $y$ 的类型以外的 4 种。

中转城市 $z$ 的位置分三种情况：

$z$ 的位置	花费	最优选择
$x < z < y$（中间）	$y - x$（最优）	存在即可
$z < x$（左边）	$x + y - 2z$	$z$ 尽量大（最靠近 $x$）
$z > y$（右边）	$2z - x - y$	$z$ 尽量小（最靠近 $y$）

数据结构

对每种类型维护一个 set<int>，用 lower_bound 快速查找最近的兼容城市。

复杂度

每次查询最多查 4 种类型，每次 $O(log n)$，总计 $O(q log n)$。

---

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 6 种类型的编号映射
    map<string, int> typeId;
    typeId["BG"] = 0; typeId["BR"] = 1; typeId["BY"] = 2;
    typeId["GR"] = 3; typeId["GY"] = 4; typeId["RY"] = 5;

    // 每种类型包含的两种颜色（B=0, G=1, R=2, Y=3）
    int col[6][2] = {{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}};

    // 预处理：类型 i 和类型 j 是否有共同颜色
    bool share[6][6];
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            share[i][j] = (col[i][0]==col[j][0] || col[i][0]==col[j][1] ||
                           col[i][1]==col[j][0] || col[i][1]==col[j][1]);

    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;

        vector<int> tp(n + 1);       // tp[i] = 城市 i 的类型编号
        set<int> S[6];                // S[t] = 类型 t 的所有城市位置

        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            tp[i] = typeId[s];
            S[tp[i]].insert(i);       // 将位置 i 加入对应类型的集合
        }

        while (q--) {
            int x, y;
            cin >> x >> y;

            // 情况 1：同一城市
            if (x == y) { cout << 0 << "\n"; continue; }

            if (x > y) swap(x, y);    // 保证 x < y
            int tx = tp[x], ty = tp[y];

            // 情况 2：直达（有共同颜色）
            if (share[tx][ty]) { cout << y - x << "\n"; continue; }

            // 情况 3：需要中转，枚举 4 种兼容类型
            int ans = INT_MAX;

            for (int tt = 0; tt < 6; tt++) {
                if (tt == tx || tt == ty) continue;  // 跳过 x 和 y 自身的类型

                auto it = S[tt].lower_bound(x);      // 第一个 >= x 的位置

                // 检查 >= x 的最近城市
                if (it != S[tt].end()) {
                    int pos = *it;
                    if (pos <= y) {
                        ans = y - x;                  // 中转在 [x,y] 内，花费 = y-x
                        break;                        // 不可能更优了，直接退出
                    } else {
                        ans = min(ans, 2 * pos - x - y);  // 中转在 y 右侧
                    }
                }

                // 检查 < x 的最近城市（最大的那个）
                if (it != S[tt].begin()) {
                    --it;
                    int pos = *it;
                    ans = min(ans, x + y - 2 * pos);  // 中转在 x 左侧
                }
            }

            cout << (ans == INT_MAX ? -1 : ans) << "\n";
        }
    }

    return 0;
}

核心总结

4 种颜色选 2 种只有 6 种搭配，且互不相容的类型对恰好互补 → 只需一个中转城市。对每种兼容类型用 set + lower_bound 找最近位置，查询 $O(log n)$。