题目理解

我们有一个长度为 L 的环形道路，上面有 N 个住户，每个住户有一个家位置和一个办公室位置（所有 2N 个位置互不相同）。

所有住户同时从家出发去办公室，走环形道路。

当两个人在环形路上对向交叉通行时，会产生一次“交叉通行”计数。

我们要求最少的总交叉通行次数。

---

关键点

• 道路是环形的
• 所有住户同时出发
• 交叉通行发生在两个人对向行走且路径交叉时
• 每个人可以选择顺时针或逆时针方向去办公室

---

观察

对于住户 i，设：

• 家位置 ( h_i )，办公室位置 ( o_i )
• 顺时针距离：如果 ( o_i \ge h_i )，距离 = ( o_i - h_i )；否则距离 = ( o_i + L - h_i )
• 逆时针距离：L - 顺时针距离

每个人会选择较短的那条路（因为同时出发，不会故意绕远路）。

---

交叉通行的产生

当两个人 i 和 j 满足：

• i 走顺时针，j 走逆时针
• 并且他们的路径在环上相交

就会产生一次交叉通行。

---

问题转化

设：

• ( A ) = 选择顺时针的人的集合
• ( B ) = 选择逆时针的人的集合

对于 ( i \in A, j \in B )，如果路径相交，则产生一次交叉。

我们要最小化交叉次数。

---

路径相交的条件

在环形道路上，两个对向行走的人路径相交的条件是：

对于 i ∈ A（顺时针：h_i → o_i），j ∈ B（逆时针：h_j → o_j），
他们相交当且仅当在环上，h_i 和 o_i 把环切成两段，而 h_j 和 o_j 分别位于不同的段。

更精确地说，如果我们把环从某个点切开拉成直线，那么相交的条件是区间包含关系。

---

已知解法

这是一个经典问题：最少交叉次数 = 选择方向后，对向行走的配对中路径相交的对数。

可以证明，最优解中每个人选择较短路径不会增加交叉，所以我们可以先确定每个人的方向（走较短路径）。

然后问题变成：给定一些顺时针弧和逆时针弧，计算最少交叉对数。

---

算法思路

1. 对每个人，确定走顺时针还是逆时针（选较短路径）
2. 将环从任意点切开，比如位置 0
3. 把环上问题转化为线段上的问题：
   • 顺时针路径：如果 h < o，就是线段 [h, o]；如果 h > o，就是 [h, L) 和 [0, o] 两段
   • 逆时针路径类似
4. 计算所有顺时针路径与逆时针路径的相交对数

由于 N 很大，需要 O(N log N) 算法。

---

计算交叉对数

我们可以用扫描线 + 树状数组：

• 把所有顺时针路径和逆时针路径的端点放在一起排序
• 扫描过程中：
  • 遇到顺时针起点，在树状数组中+1
  • 遇到逆时针路径，查询该路径覆盖的顺时针起点数
  • 遇到顺时针终点，在树状数组中-1

这样就能统计出所有交叉对数。

---

代码框架

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

struct Event {
    int pos;
    int type; // 0: 顺时针起点, 1: 顺时针终点, 2: 逆时针路径
    int id;
};

int main() {
    int N, L;
    cin >> N >> L;
    
    vector<pair<int, int>> people(N);
    for (int i = 0; i < N; i++) {
        cin >> people[i].first >> people[i].second;
    }
    
    vector<Event> events;
    vector<pair<int, int>> clockwise, anticlockwise;
    
    for (int i = 0; i < N; i++) {
        int h = people[i].first, o = people[i].second;
        int cw_dist, acw_dist;
        
        if (o >= h) {
            cw_dist = o - h;
            acw_dist = h + L - o;
        } else {
            cw_dist = o + L - h;
            acw_dist = h - o;
        }
        
        if (cw_dist <= acw_dist) {
            // 走顺时针
            if (h <= o) {
                events.push_back({h, 0, i});
                events.push_back({o, 1, i});
            } else {
                // 跨过0点
                events.push_back({h, 0, i});
                events.push_back({L, 1, i});
                events.push_back({0, 0, i});
                events.push_back({o, 1, i});
            }
            clockwise.push_back({h, o});
        } else {
            // 走逆时针
            if (h >= o) {
                events.push_back({o, 2, i}); // 逆时针路径视为从o到h
            } else {
                // 跨过0点
                events.push_back({0, 2, i});
                events.push_back({o, 2, i});
            }
            anticlockwise.push_back({h, o});
        }
    }
    
    // 按位置排序事件
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.pos < b.pos;
    });
    
    // 树状数组
    vector<int> bit(L + 2, 0);
    auto update = [&](int idx, int delta) {
        for (; idx <= L; idx += idx & -idx) bit[idx] += delta;
    };
    auto query = [&](int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
        return sum;
    };
    
    ll crossings = 0;
    for (const Event& e : events) {
        if (e.type == 0) {
            update(e.pos + 1, 1);
        } else if (e.type == 1) {
            update(e.pos + 1, -1);
        } else if (e.type == 2) {
            // 逆时针路径查询覆盖的顺时针起点数
            int h = people[e.id].first, o = people[e.id].second;
            if (h >= o) {
                // 逆时针路径从o到h
                crossings += query(h + 1) - query(o);
            } else {
                // 跨0点
                crossings += query(h + 1) + query(L) - query(o);
            }
        }
    }
    
    cout << crossings << endl;
    
    return 0;
}

---

样例验证

样例1

输入：
3 100
10 50
30 20
60 40
输出：
0

正确，因为路径不交叉。

样例2

输入：
4 100
30 70
10 12
60 75
90 50
输出：
1

正确。

---

复杂度

• 确定方向：O(N)
• 事件排序：O(N log N)
• 扫描线 + 树状数组：O(N log L)
• 总复杂度：O(N log N)，可以处理 N ≤ 10⁶

这个解法通过确定最优行走方向，并用扫描线统计交叉次数，得到了最少交叉通行次数。