分析

转化

考虑两条线段 $i$ 和 $j$。我们将它们在 $x$ 轴上的端点坐标记为 $A_i, A_j$，在顶部直线 $y = H$ 上的端点坐标记为 $B_i, B_j$。

题目保证所有 $A_i$ 互不相同，所有 $B_i$ 也互不相同。因此，线段 $i$ 和线段 $j$ 在同一个坐标系中不相交，当且仅当它们的端点在 $x$ 轴上的顺序与在 $y = H$ 上的顺序相同。

简单来说，如果我们把线段按照 $A_i$（即 $x$ 轴坐标）从小到大排序，那么它们对应的 $B_i$（即顶部坐标）也必须是单调递增的，否则就会出现交叉。

形式化地，对于两条线段 $i$ 和 $j$，假设 $A_i < A_j$。它们不相交的充要条件是 $B_i < B_j$。如果 $B_i > B_j$，则这两条线段必然相交。

例如，对于输入：

1 3
3 1

第一条线段连接 $(1, 0)$ 和 $(3, H)$，第二条线段连接 $(3, 0)$ 和 $(1, H)$。 这里有 $A_1 = 1 < A_2 = 3$，但 $B_1 = 3 > B_2 = 1$。因此它们在同一个坐标系中会相交，必须分开放置，所以答案是 $2$。

序列问题

根据上述分析，问题转化如下：

将所有线段按底部端点坐标 $X_{i,1}$ 升序排序，得到一个新的顶部端点坐标的序列 $\{B_1, B_2, \dots, B_N\}$。我们要将这个序列划分成尽可能少的子序列，使得每个子序列都是严格递增的。

根据 Dilworth 定理，一个序列最少能划分成的递增子序列的数量，等于其最长不升子序列的长度。因此，我们的目标就是求出排序后序列 $\{B_i\}$ 的最长不升子序列的长度。

由于 $N \le 10^5$，我们需要一个 $\mathcal{O}(N \log N)$ 的算法。

实现

我们使用经典的贪心加二分的方法。

设原数组为 $B$，我们希望找到 $B$ 的最长不升子序列。将其取反得到数组 $C$，其中 $C_i = -B_i$。那么 $B$ 的一个不升子序列 $B_{i_1} \ge B_{i_2} \ge \dots$ 对应到 $C$ 上就是 $-B_{i_1} \le -B_{i_2} \le \dots$，这是一个不降子序列。

因此，原问题转化为求数组 $C$ 的最长不降子序列（LNDS）。

对于 LNDS，我们维护一个数组 $\textit{dp}$，其中 $\textit{dp}_k$ 表示当前找到的长度为 $k$ 的不降子序列的最小末尾元素。当我们处理一个新元素 $x$ 时，在 $\textit{dp}$ 中二分查找第一个大于 $x$ 的位置。如果存在，则用 $x$ 替换该元素；否则将 $x$ 追加到 $\textit{dp}$ 末尾。

最终 $\textit{dp}$ 的长度即为答案。

细节说明：由于题目保证所有的 $X_{i,2}$ 互不相同，序列 $C$ 中没有重复元素，此时不降子序列等价于严格上升子序列。因此，可以使用 std::lower_bound 来求最长上升子序列的长度，这与求最长不降子序列在本题条件下是等价的。

代码

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define bye return 0
#define hello ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define i_ak_all int main()
using namespace std;

i_ak_all{
	hello;

	ll n;
	cin >> n;
	vector<ll> b(n), dp;
	vector<pair<ll, ll>> a(n);
	for (auto & x : a){
		cin >> x.first >> x.second;
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++){
		b[i] = -a[i].second;
	}
	for (ll x : b){
		auto it = lower_bound(dp.begin(), dp.end(), x);
		if (it == dp.end()){
			dp.push_back(x);
		}
		else {
			*it = x;
		}
	}
	cout << dp.size();

	bye;
}

AI 使用说明：

本文在写作完成后使用 DeepSeek 进行了润色。