问题分析

有 $2N$ 个学生站成一个圆圈，编号为 $0$ 到 $2N-1$。学生之间的认识关系包括：

1. 相邻关系：学生 $i$ 认识 $i-1$ 和 $i+1$（模 $2N$）
2. 闺蜜关系：有 $M$ 对闺蜜，第 $i$ 对分别站在位置 $k_i$ 和 $k_i+N$

需要回答 $Q$ 次查询：从学生 $x$ 到学生 $y$ 的最短传球路径长度。

关键观察

1. 图形结构：这实际上是一个环形图加上 $M$ 条"直径边"

   • 环形边：相邻学生之间的边
   • 直径边：闺蜜对之间的边（连接相对位置）

2. 路径性质：最短路径要么：

   • 直接沿着环形走（不经过闺蜜边）
   • 经过恰好一条闺蜜边（使用一个"传送门"）

3. 贪心选择：如果使用闺蜜边，应该选择离起点最近的闺蜜位置

算法思路

1. 距离计算

在环形上，两点 $x$ 和 $y$ 之间的最短距离为：

$$\text{dist}(x, y) = \min(|x-y|, 2N - |x-y|)$$

2. 传送门处理

对于每个闺蜜对 $(k, k+N)$，我们将其视为两个"传送门"：

• 位置 $k$ 的传送门可以跳到 $k+N$
• 位置 $k+N$ 的传送门可以跳到 $k$

3. 查询计算

对于查询 $(x, y)$：

1. 计算直接距离：$\text{dist}(x, y)$
2. 找到离 $x$ 最近的传送门 $p$（使用二分查找）
3. 计算通过传送门的距离：$\text{dist}(x, p) + 1 + \text{dist}(\text{配对}(p), y)$
4. 取最小值

代码详解

#include <bits/stdc++.h>

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    
    // 存储所有传送门位置（每个闺蜜对有两个传送门）
    std::vector<int> portals(m + m);
    
    for (int i = 0; i < m; ++i) {
        int x;
        scanf("%d", &x);
        portals[i] = x;           // 位置 k
        portals[i + m] = x + n;   // 位置 k+N
    }
    
    // 环形距离计算函数
    auto dist = [&](int x, int y) -> int {
        if (x < y) std::swap(x, y);
        // 两种走法：直接走 or 绕远路
        return std::min(x - y, n + n + y - x);
    };
    
    // 通过传送门的距离计算
    auto dist_by_portal = [&](int x, int y, int z) -> int {
        // z: 传送门位置
        // 配对传送门：如果 z ≤ n 则配对是 z+n，否则是 z-n
        int paired = (z <= n) ? (z + n) : (z - n);
        return dist(x, z) + 1 + dist(paired, y);
    };
    
    // 对传送门位置排序，便于二分查找
    std::sort(portals.begin(), portals.end());
    
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        
        // 方案1：直接传球（不经过传送门）
        int ans = dist(x, y);
        
        // 找到离 x 最近的传送门
        // lower_bound 返回第一个 ≥ x 的位置
        int i = std::lower_bound(portals.begin(), portals.end(), x) - portals.begin();
        
        // 方案2：使用右边最近的传送门
        if (i == portals.size()) {
            // x 比所有传送门都大，用第一个传送门（环形）
            ans = std::min(ans, dist_by_portal(x, y, portals.front()));
        } else {
            ans = std::min(ans, dist_by_portal(x, y, portals[i]));
        }
        
        // 方案3：使用左边最近的传送门
        if (i == 0) {
            // x 比所有传送门都小，用最后一个传送门（环形）
            ans = std::min(ans, dist_by_portal(x, y, portals.back()));
        } else {
            ans = std::min(ans, dist_by_portal(x, y, portals[i - 1]));
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}

复杂度分析

• 预处理：

  • 构建传送门数组：$O(M)$
  • 排序：$O(M \log M)$

• 每次查询：

  • 二分查找：$O(\log M)$
  • 距离计算：$O(1)$

• 总复杂度：$O(M \log M + Q \log M)$

正确性证明

为什么最多只需要使用一个传送门？

假设使用两个传送门 $p_1$ 和 $p_2$，路径为：

$$x \to p_1 \to \text{pair}(p_1) \to p_2 \to \text{pair}(p_2) \to y $$

这等价于：

$$x \to p_1 \to \text{pair}(p_2) \to y$$

其中 $\text{pair}(p_1)$ 到 $p_2$ 的路径可以合并到环形路径中。因此使用一个传送门不会更差。

为什么只需要检查最近的传送门？

设 $p$ 是离 $x$ 最近的传送门，$p'$ 是另一个传送门。

• 如果 $p'$ 在 $x$ 和 $p$ 之间：那么 $\text{dist}(x, p') < \text{dist}(x, p)$，但 $\text{dist}(\text{pair}(p'), y)$ 可能更大
• 由于环形对称性，检查 $p$ 及其相邻的两个传送门足够覆盖所有情况