題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC439E Kite

Problem Statement

題目簡述

$N$ 個人在河岸邊放風箏。第 $i$ 個人站在點 $(A_i, 0)$ ，其風箏位於點 $(B_i, 1)$ 。

若兩人的風箏線（連接人與風箏的線段）有交點（包含端點接觸），則他們不能同時放風箏。

求最多能有多少人同時放風箏。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i, B_i \leq 10^9$

思路：二維LIS

問題轉化：線段不相交的條件

每個人 $i$ 對應一條從 $(A_i, 0)$ 到 $(B_i, 1)$ 的線段。我們需要找出最大的人數集合，使得這些人的線段兩兩不相交。

線段不相交的條件

考慮兩個人 $i$ 和 $j$ ，假設 $A_i < A_j$ （人 $i$ 站得更靠左）：

若 $B_i < B_j$ ：線段 $i$ 整體在線段 $j$ 的「左邊」，不相交 ✓
若 $B_i \geq B_j$ ：線段會在中間交叉，相交 ✗

因此，不相交的條件是： $A_i < A_j \Rightarrow B_i < B_j$

轉化為 LIS

將所有人按 $A_i$ 由小到大排序後，問題變成：

在排序後的序列中，選擇最多的人，使得他們的 $B_i$ 值嚴格遞增。

這正是 最長嚴格遞增子序列 (Longest Strictly Increasing Subsequence, LIS) 問題！

處理 $A$ 相同的情況

當 $A_i = A_j$ 時，這兩條線段的起點相同（端點接觸），因此也算相交，不能同時選取。

排序的關鍵技巧

排序時使用 key = (A_i, -B_i)：

主鍵 $A_i$ 升序
次鍵 $-B_i$ （即 $B_i$ 降序）

這樣處理的目的是：當 $A$ 相同時， $B$ 較大的在前面先被處理。由於我們求的是嚴格遞增的 LIS，同一個 $A$ 值下最多只會有一個被選入。

使用二分搜尋優化 LIS

程式碼使用經典的二分搜尋優化 LIS 算法：

維護陣列 f，其中 f[i] 表示長度為 $i+1$ 的 LIS 的最小末尾元素
對每個 $B_i$ ，使用 bisect_left 找到插入位置並更新 f
最終 len(f) 即為 LIS 的長度

複雜度分析

時間複雜度： $\mathcal{O}(N \log N)$ （排序 + 二分搜尋 LIS）
空間複雜度： $\mathcal{O}(N)$ （儲存輸入和 LIS 陣列）

Code

from bisect import bisect_left

def solve():
    n = int(input())
    P = [tuple(map(int, input().split())) for _ in range(n)]
    assert len(P) == n

    P.sort(key=lambda x: (x[0], -x[1]))
    f = []
    for _, b in P:
        idx = bisect_left(f, b)
        if idx == len(f):
            f.append(b)
        else:
            f[idx] = b
    print(len(f))

if __name__ == '__main__':
    solve()