友好城市问题：从二维偏序到最长上升子序列的转化与实现

1. 从"友好城市"这个标题说起：它到底在考什么

第一次看到"友好城市"这个题目名，很多人会以为是图论或者并查集，毕竟"城市"两个字太容易让人联想到连通性、最短路这些经典模型。但真正把题目读完就会发现，它其实是一道非常典型的最长上升子序列（LIS）变形题，只不过套了一层"配对"的外衣。

题目的核心场景是这样的：河的两岸各有若干个城市，北岸城市和南岸城市之间存在若干条"友好关系"航线。现在要在这条河上修桥，要求任意两座桥不能交叉。问最多能修多少座桥。

这个"不能交叉"的约束，就是整道题的灵魂。它把一个看起来像二分图匹配的问题，硬生生转化成了一个一维的序列问题。为什么？因为一旦你按某一岸的城市坐标排序，另一岸对应的坐标就必须满足单调性，否则两座桥必然交叉。

我见过太多人在这道题上卡住，不是因为不会写LIS，而是因为没想通"排序"这一步为什么能成立。他们要么直接上二分图匈牙利算法，要么试图用区间DP去枚举，结果要么超时，要么状态设计错误。其实这道题一旦想通转化逻辑，代码量不到三十行。

这篇文章我会从"为什么排序能消除交叉约束"讲起，把转化过程拆到每一步都能自己复现，然后给出LIS的两种写法（朴素O(n²)和二分O(n log n)），再补充几个实际写代码时容易踩的坑，比如坐标重复、排序方向、边界初始化。适合正在刷算法题、想搞懂LIS类变形题的读者，也适合已经会写LIS但一遇到应用题就懵的人。

2. 为什么"桥不能交叉"等价于"序列单调"

2.1 用几何直觉理解交叉条件

先把场景画在脑子里：一条河横在中间，北岸是一条直线，南岸是另一条平行直线。北岸城市用坐标 x₁ 表示，南岸城市用坐标 x₂ 表示。一座桥连接北岸的 a 和南岸的 b，在图上就是一条线段。

现在考虑两座桥：桥1连接 (a₁, b₁)，桥2连接 (a₂, b₂)。假设在北岸方向上 a₁ < a₂。如果这两座桥不交叉，那么在南岸方向上必须也有 b₁ < b₂。反过来，如果 b₁ > b₂，那么从 a₁ 出发的线要连到更靠右的 b₁，从 a₂ 出发的线要连到更靠左的 b₂，两条线段必然在河面上相交。

这个结论可以用初中的几何知识验证：两条线段如果端点分别在两条平行线上，且端点顺序相反，那么它们一定相交。这不是概率问题，是必然的。

所以"所有桥互不交叉"这个约束，翻译成数学语言就是：如果按北岸坐标从小到大排序，那么对应的南岸坐标必须严格递增。

2.2 排序是消除交叉约束的关键操作

很多人会问：为什么一定要排序？不排序行不行？

不排序的话，你面对的是一个二维的配对选择问题：从若干对 (a, b) 中选出最多的对，使得不存在 i, j 满足 aᵢ < aⱼ 且 bᵢ > bⱼ。这是一个典型的二维偏序问题，直接做需要树状数组或者CDQ分治。

但如果我们先按北岸坐标排序，那么 a 这一维就自动有序了。此时只需要保证 b 递增，就等价于原约束。问题从二维降到了一维，这就是排序的价值。

注意：排序之后，我们实际上是在"北岸有序"的前提下做选择。因为桥的修建不要求覆盖所有城市，只要求选出的桥互不交叉，所以排序不会丢失任何可行解——任何一组互不交叉的桥，按北岸坐标排序后，南岸坐标必然也是递增的。

2.3 从配对到序列：问题转化的完整链路

把转化过程完整写一遍：

1. 读入所有友好关系对 (a, b)，表示北岸城市 a 和南岸城市 b 可以修桥。
2. 按 a 从小到大排序。如果 a 相同，按 b 从小到大排序（这一点后面会详细讲为什么）。
3. 取出排序后的 b 序列。
4. 问题变成：在这个 b 序列中，最多能选出多少个元素，使得它们严格递增。
5. 这就是最长上升子序列问题。

整个转化的核心在于第2步和第4步。第2步把二维约束压成一维，第4步把"选桥"变成"选递增子序列"。想通这两步，剩下的就是LIS模板。

3. 最长上升子序列的两种写法与选择依据

3.1 朴素DP：O(n²)的写法与适用场景

LIS最直观的写法是动态规划。定义 dp[i] 表示以第 i 个元素结尾的最长上升子序列长度。转移方程：

dp[i] = max(dp[j]) + 1, 其中 j < i 且 b[j] < b[i]

初始时每个 dp[i] = 1，因为至少可以选自己。

代码实现：

def lis_n2(arr): n = len(arr) if n == 0: return 0 dp = [1] * n for i in range(n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

这个写法的时间复杂度是 O(n²)，空间 O(n)。当 n 在几千以内时完全够用。它的优点是逻辑直白，不容易写错，而且方便记录具体选了哪些元素（如果需要输出方案的话）。

我一般建议：如果题目数据范围 n ≤ 5000，直接用这个写法，省事。AcWing上这道题的数据范围通常在几千，O(n²)能过。

3.2 二分+贪心：O(n log n)的优化思路

如果 n 到了十万级别，O(n²)就危险了。这时候需要用二分优化。

核心思想是维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的上升子序列的末尾元素的最小值。这个数组有一个重要性质：它一定是严格递增的。

为什么？假设 tails[k] ≥ tails[k+1]，那么长度为 k+2 的上升子序列的倒数第二个元素一定小于 tails[k+1]，也就小于 tails[k]，那长度为 k+1 的子序列末尾可以更小，矛盾。

基于这个性质，对于每个新元素 x，我们可以在 tails 中二分找到第一个大于等于 x 的位置，替换它。如果 x 比所有元素都大，就追加到末尾。

import bisect def lis_nlogn(arr): tails = [] for x in arr: pos = bisect.bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails)

这里用 bisect_left 而不是 bisect_right，是因为我们要求严格递增。如果允许非严格递增（即可以相等），就要用 bisect_right。

提示：tails 数组本身并不是某个具体的上升子序列，它只是记录了每个长度对应的最小末尾值。最终 tails 的长度就是LIS的长度，但 tails 里的元素不一定构成原序列中的合法子序列。这一点经常有人搞混。

3.3 两种写法的对比与选型建议

我的建议是：平时刷题两种都写一遍，理解它们的等价性。比赛时看数据范围选。如果时间紧，直接背二分版本，因为它适用范围更广。

4. 排序细节：相同坐标到底怎么处理

4.1 北岸坐标相同时的排序方向

这是这道题最容易出错的地方之一。

假设有两对关系：(a=1, b=5) 和 (a=1, b=3)。北岸坐标相同，都是1。这两座桥能同时修吗？

从几何上看，两座桥都从北岸的同一个点出发，连到南岸的不同点。它们只在北岸端点重合，在河面上并不交叉（除非认为共端点算交叉）。但题目通常要求桥不能交叉，共端点是否允许取决于题意。

在AcWing 1012这道题中，通常认为同一个北岸城市只能修一座桥，因为一个城市修两座桥到两个不同城市，这两座桥共享端点，在实际场景中不太合理。但题目输入可能不会出现重复的北岸坐标，或者即使出现，我们也可以通过排序策略来处理。

关键点：如果按 a 升序，a 相同时按 b 升序，那么在 b 序列中，相同 a 对应的 b 是递增的。此时如果LIS允许严格递增，这些 b 可以同时被选中，意味着同一个北岸城市修了多座桥。如果题目不允许，就需要在排序时让 a 相同时 b 降序，这样在LIS中它们不可能同时被选（因为后面的 b 更小，不满足递增）。

4.2 南岸坐标重复的影响

如果两个不同的北岸城市 a₁ < a₂，但对应的 b 相同，即 b₁ = b₂。这两座桥能同时修吗？

从几何上看，两座桥从不同北岸点出发，连到南岸同一个点。它们在南岸端点重合。同样，是否允许取决于题意。

如果要求严格不交叉且不共端点，那么 b 必须严格递增，相等的 b 不能同时选。此时LIS用严格递增即可。

如果允许共端点，那么 b 可以非严格递增，LIS用非严格递增。

注意：AcWing 1012的标准题意是桥不能交叉，通常理解为不能有公共点（包括端点），所以用严格递增。但实际写题时要看清题目描述。如果题目说"任意两座桥不能相交"，一般包含端点相交。

4.3 一个具体的排序+去重案例

假设输入关系为：(1,3), (1,5), (2,4), (2,6), (3,5)。

按 a 升序，a 相同按 b 升序排序后：b序列为 [3,5,4,6,5]。

如果直接用严格递增LIS，结果是 [3,4,6] 或 [3,4,5]，长度为3。这意味着选了 (1,3), (2,4), (3,5) 或 (1,3), (2,4), (2,6)？等等，(2,4)和(2,6)的a相同，不能同时选。但LIS选的是b序列中的元素，b=4和b=6对应的是a=2的两个不同关系。如果LIS同时选了它们，就表示北岸城市2修了两座桥，这通常是不允许的。

所以如果题目限制一个城市只能修一座桥，我们需要在排序时对相同a的处理做文章。具体做法：按a升序，a相同时按b降序。这样b序列变成 [5,3,6,4,5]。此时LIS严格递增的结果是 [3,4,5] 或 [3,4,6]？实际上[5,3,6,4,5]的严格递增LIS是[3,4,5]或[3,4,6]？让我算一下：3,4,5是递增的，对应(1,5)?不对，3对应(1,5)？排序后是(1,5),(1,3),(2,6),(2,4),(3,5)，b序列[5,3,6,4,5]。LIS可以是[3,4,5]，对应(1,3),(2,4),(3,5)，a分别是1,2,3，没有重复，正确。

所以关键结论：如果题目要求每个城市最多修一座桥，排序时a相同按b降序；如果允许一个城市修多座桥（只要不交叉），按b升序。

AcWing 1012的输入通常保证北岸城市坐标互不相同，或者题意默认一个城市只修一座桥。保险起见，我建议按a升序、a相同按b降序来排序，这样LIS严格递增就能自动保证每个a只选一次。

5. 完整代码实现与逐行注释

5.1 Python版本：从读入到输出

import sys import bisect def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) pairs = [] idx = 1 for _ in range(n): a = int(data[idx]) b = int(data[idx+1]) idx += 2 pairs.append((a, b)) # 按北岸坐标升序，相同则按南岸坐标降序 pairs.sort(key=lambda x: (x[0], -x[1])) # 提取南岸坐标序列 b_seq = [p[1] for p in pairs] # 二分法求严格递增LIS tails = [] for x in b_seq: pos = bisect.bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x print(len(tails)) if __name__ == "__main__": main()

这段代码的输入格式假设是：第一行一个整数n，接下来n行每行两个整数a和b。如果实际输入格式不同，需要调整读入部分。

5.2 C++版本：适合竞赛环境

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int,int>> pairs(n); for (int i = 0; i < n; i++) { cin >> pairs[i].first >> pairs[i].second; } sort(pairs.begin(), pairs.end(), [](const pair<int,int>& x, const pair<int,int>& y) { if (x.first != y.first) return x.first < y.first; return x.second > y.second; }); vector<int> tails; for (auto& p : pairs) { int x = p.second; auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); } else { *it = x; } } cout << tails.size() << endl; return 0; }

C++的 lower_bound 默认是找第一个大于等于x的位置，正好对应严格递增LIS。如果要用非严格递增，改成 upper_bound。

5.3 边界情况与初始化检查

几个必须检查的边界：

• n = 0：没有友好关系，输出0。代码中tails为空，输出0，正确。
• n = 1：只有一对关系，输出1。tails会有一个元素，正确。
• 所有b相同：比如b序列[3,3,3]，严格递增LIS长度为1。bisect_left每次都会替换第一个位置，tails长度保持1，正确。
• b序列已经严格递增：比如[1,2,3,4]，每次x都大于tails末尾，直接append，长度4，正确。
• b序列严格递减：比如[4,3,2,1]，每次x都替换tails[0]，长度1，正确。

提示：如果题目要求输出具体选了哪些桥，需要在DP版本中记录前驱，二分版本则需要额外维护一个数组记录每个元素在LIS中的位置。但AcWing 1012只要求输出最大数量，所以不需要。

6. 实际写题时踩过的坑与排查思路

6.1 排序方向写反导致答案偏小

我第一次写这道题时，按a升序、a相同按b升序排序，结果在某些测试数据上答案比预期小。排查了半天才发现，当a相同时，b升序会让LIS可能同时选中同一个a的多个b，但题目不允许一个城市修多座桥。改成b降序后，同一个a的b在序列中递减，LIS严格递增就不可能同时选中它们。

这个坑的排查方法：构造一组有重复a的数据，手动模拟LIS过程，看是否会选中同一个a的多个b。如果会，就说明排序方向需要调整。

6.2 严格递增与非严格递增混用

另一个常见错误是LIS的严格性搞错。如果题目允许桥共端点，那么b可以相等，此时应该用非严格递增LIS（bisect_right）。如果题目不允许共端点，用严格递增（bisect_left）。

我建议先按严格递增写，如果答案偏小，再考虑是否题目允许共端点。但AcWing 1012的标准题意是严格不交叉，所以严格递增是对的。

6.3 输入格式与多组数据的处理

有些平台的输入可能包含多组测试数据，或者n和关系对在同一行。这时候用 sys.stdin.read().split() 一次性读入所有token是最稳妥的，避免逐行读取时格式不一致的问题。

如果题目明确只有一组数据，也可以逐行读。但竞赛中我习惯用read().split()，省心。

6.4 数据范围导致的超时问题

如果n到了10⁵，O(n²)的DP会超时。这时候必须用二分版本。我一般直接写二分版本，因为它的代码量也不大，而且不用担心数据范围。

如果n到了10⁶，二分版本的O(n log n)也可能吃力，但一般算法题不会给这么大。真到了这个级别，需要考虑更高级的数据结构或者题目本身有特殊性质。

7. 从这道题延伸出去的同类问题

7.1 最长不下降子序列的变体

把严格递增改成非严格递增，就是最长不下降子序列。处理方法很简单：二分时用 upper_bound 代替 lower_bound。在排序时，如果a相同按b升序，配合非严格递增LIS，也能处理某些允许共端点的场景。

7.2 二维偏序与导弹拦截问题

"友好城市"本质上是二维偏序的一个特例。更一般的二维偏序问题是：给定若干点 (x, y)，求最多能选出多少个点使得x和y都递增。如果x已经有序，就退化成LIS。如果x无序，就需要先排序再LIS，或者用树状数组。

经典的"导弹拦截"问题也是LIS的变形：第一问求最长不上升子序列，第二问求最少的不上升子序列覆盖数，后者等价于最长上升子序列长度（Dilworth定理）。

7.3 排序+LIS的通用解题框架

遇到"选最多元素满足某种单调性"的问题，可以套这个框架：

1. 确定哪个维度可以排序，排序后该维度自动满足约束。
2. 把另一个维度提取成序列。
3. 根据约束的严格性选择LIS的严格/非严格版本。
4. 注意相同第一维时的排序方向，避免选中不允许的组合。

这个框架能解决一大类问题，包括区间调度、信封嵌套、俄罗斯套娃等。

7.4 与二分图匹配的区别

有人会想：这不是二分图最大匹配吗？北岸城市和南岸城市配对，要求边不交叉。但二分图匹配求的是最大匹配数，不考虑边的几何交叉。如果加上不交叉约束，就不能直接用匈牙利算法，因为匹配算法不知道几何信息。

实际上，"不交叉"约束把问题从一般的二分图匹配降到了LIS，这是约束带来的福利。如果没有这个约束，问题会难得多。

8. 我个人在这道题上的经验总结

刷这道题最大的收获不是学会了LIS，而是理解了排序如何消除维度约束。很多算法题看起来复杂，其实就差一个排序。排序之后，原本需要二维数据结构的问题变成了一维，原本需要复杂状态设计的问题变成了模板题。

另一个体会是：不要急着写代码，先把转化逻辑想清楚。我见过太多人一看到"城市"就往上套图论，结果绕了一大圈才发现是LIS。花五分钟想清楚问题的本质，比花半小时调试错误代码划算得多。

最后说一个实用技巧：写完LIS后，用几组小数据手动验证。比如n=3，关系为(1,3),(2,2),(3,1)，排序后b序列[3,2,1]，LIS长度为1，意味着最多修一座桥。这符合直觉：三座桥的b递减，任意两座都会交叉。再比如(1,1),(2,2),(3,3)，b序列[1,2,3]，LIS长度为3，三座桥都不交叉。用这种极端数据验证，能快速发现排序或LIS写法的错误。

如果后续想扩展，可以尝试输出具体的建桥方案，或者处理带权重的版本（每座桥有收益，求最大收益）。带权版本就不能直接用LIS了，需要变成最大权上升子序列，用树状数组优化DP。那是另一个话题了。