2678. 「BalticOI 2010」PCB 题解

问题分析

我们有 N 条电线，每条电线连接底部点 $(X_{i1}, 0)$ 和顶部点 $(X_{i2}, H)$。每条电线是一条直线段。

关键规则：

1. 同一层中的电线不能交叉
2. 不同层的电线可以交叉（因为中间有绝缘层）
3. 需要最小化层数

问题转化：

• 电线 $i$ 由两个端点 $(X_{i1}, 0)$ 和 $(X_{i2}, H)$ 定义
• 如果两条电线在同一个层，它们不能交叉
• 将电线分配到不同层，使每层的电线都不交叉
• 求最小层数

关键观察

1. 交叉条件

两条电线 $i$ 和 $j$ 交叉当且仅当：

$$(X_{i1} - X_{j1}) \times (X_{i2} - X_{j2}) < 0$$

即：一个端点的相对顺序在底部和顶部相反。

2. 问题重述

我们需要将电线分成若干不交叉的子集（每个子集放一层），使得子集数最小。

这不就是图着色问题吗？交叉的电线不能同色，求最小色数。

但 N 最多 $10^5$，直接建图是 $O(N^2)$ 会超时。

3. Dilworth 定理应用

将电线按底部端点 $X_{i1}$ 排序（因为端点互不相同，可以唯一排序）。

定义偏序关系：电线 $i < j$ 如果 $X_{i1} < X_{j1}$ 且 $X_{i2} < X_{j2}$。

重要发现：

• 如果 $i < j$ 在偏序中，那么 $i$ 和 $j$ 不会交叉（它们在底部和顶部的顺序相同）
• 如果 $i$ 和 $j$ 不可比较（即一个端点大，另一个端点小），那么它们交叉

问题等价于：将电线划分成若干条链（全序集），使得链中任意两条电线都不交叉。

根据 Dilworth 定理：最小链划分 = 最大反链大小

在这里：

• 链：一组两两可比较的电线（都不交叉）
• 反链：一组两两不可比较的电线（都互相交叉）

所以：最小层数 = 最大互相交叉的电线数

算法思路

1. 按底部端点排序

先将所有电线按 $X_{i1}$ 从小到大排序。

2. 问题转化为 LIS

排序后，问题变为： 在序列 $X_{i2}$ 中，找到最长下降子序列（LDS）的长度。

为什么？

• 排序后，底部端点已经有序
• 对于电线 $i$ 和 $j$（$i < j$）：
  • 如果 $X_{i2} > X_{j2}$，则它们交叉（因为底部顺序：$i$ 在 $j$ 左边，但顶部：$i$ 在 $j$ 右边）
  • 如果 $X_{i2} < X_{j2}$，则不交叉
• 一组互相交叉的电线 ⇒ 在排序后的序列中，它们的 $X_{i2}$ 值严格递减
• 最大互相交叉的电线数 = 最长严格递减子序列的长度

3. 计算方法

求最长严格递减子序列（LDS）的长度。

由于 N 最大 $10^5$，$X_{i2}$ 范围 $[0, 10^6]$，可以用：

• $O(N \log N)$ 的贪心 + 二分
• 或用树状数组优化

详细算法

方法1：贪心 + 二分 $O(N \log N)$

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

int main() {
    int N;
    cin >> N;
    
    vector<pair<int, int>> wires(N);
    for (int i = 0; i < N; i++) {
        cin >> wires[i].first >> wires[i].second;
    }
    
    // 按底部端点排序
    sort(wires.begin(), wires.end());
    
    // 求最长严格递减子序列的长度
    vector<int> tails;  // tails[k] = 长度为k+1的递减子序列的最小末尾值
    
    for (int i = 0; i < N; i++) {
        int top = wires[i].second;
        
        // 在tails中找第一个小于top的位置（因为要严格递减）
        // tails是递减的，所以用lower_bound要找第一个<top的
        // 但我们通常维护递增序列，找第一个≥top的
        
        // 更简单：我们维护一个递增序列，但存储负值
        top = -top;  // 取负，将递减问题转化为递增问题
        
        auto it = lower_bound(tails.begin(), tails.end(), top);
        if (it == tails.end()) {
            tails.push_back(top);
        } else {
            *it = top;
        }
    }
    
    cout << tails.size() << endl;
    return 0;
}

方法2：离散化 + 树状数组 $O(N \log N)$

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

class FenwickTree {
private:
    vector<int> tree;
    int n;
    
public:
    FenwickTree(int size) : n(size) {
        tree.resize(n + 1, 0);
    }
    
    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] = max(tree[idx], val);
            idx += idx & -idx;
        }
    }
    
    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res = max(res, tree[idx]);
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    int N;
    cin >> N;
    
    vector<pair<int, int>> wires(N);
    vector<int> all_values;
    
    for (int i = 0; i < N; i++) {
        cin >> wires[i].first >> wires[i].second;
        all_values.push_back(wires[i].second);
    }
    
    // 离散化顶部端点
    sort(all_values.begin(), all_values.end());
    all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
    
    auto get_rank = [&](int value) {
        return lower_bound(all_values.begin(), all_values.end(), value) - all_values.begin() + 1;
    };
    
    // 按底部端点排序
    sort(wires.begin(), wires.end());
    
    // 由于我们要找递减子序列，可以将值取反
    int m = all_values.size();
    FenwickTree bit(m);
    
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int top = wires[i].second;
        // 对于递减子序列，我们关心比当前值大的
        // rank越大表示值越大
        int rank = get_rank(top);
        // 比当前值大的都在rank+1..m范围内
        // 但由于树状数组查询前缀，我们将值取反
        int rev_rank = m - rank + 1;  // 值越大，rev_rank越小
        
        int len = bit.query(rev_rank - 1) + 1;  // 比当前值大的最长序列长度
        ans = max(ans, len);
        bit.update(rev_rank, len);
    }
    
    cout << ans << endl;
    return 0;
}

正确性证明

1. 为什么是最长递减子序列？

• 按底部端点排序后，底部顺序固定
• 如果一组电线互相交叉，那么对于其中任意两条 $i < j$（按底部排序），必须有 $X_{i2} > X_{j2}$
• 因此这组电线的顶部端点值严格递减
• 反之，一组顶部端点严格递减的电线一定互相交叉
• 所以最大互相交叉的电线数 = 最长严格递减子序列的长度

2. 为什么最小层数等于最大互相交叉数？

根据 Dilworth 定理：

• 偏序集：电线按 $(X_{i1}, X_{i2})$ 排序
• 链：一组两两可比较的电线（都不交叉）
• 反链：一组两两不可比较的电线（都互相交叉）
• 最小链划分数 = 最大反链大小

在这里，链对应可以放在同一层的电线组，所以最小层数 = 最大反链大小 = 最大互相交叉的电线数。

复杂度分析

• 排序：$O(N \log N)$
• 求 LDS：$O(N \log N)$
• 总复杂度：$O(N \log N)$
• 空间：$O(N)$

示例验证

样例1

2
1 1
3 3

排序后顶部端点：[1, 3]（递增） 最长递减子序列长度 = 1 输出：1 ✓

样例2

2
1 3
3 1

排序后顶部端点：[3, 1]（递减） 最长递减子序列长度 = 2 输出：2 ✓

总结

本题的关键转化：

1. 将物理交叉问题转化为偏序关系
2. 应用 Dilworth 定理，将最小层数问题转化为最大反链问题
3. 发现最大互相交叉的电线数就是最长递减子序列的长度
4. 用 $O(N \log N)$ 算法求解