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

🔗 ABC410G Longest Chord Chain

Problem Statement

題目簡述

圓周上有 $2N$ 個點（依順時針為 $1,2,\dots,2N$ ），給定 $N$ 條弦，第 $i$ 條連接 $A_i,B_i$ ，且所有端點兩兩不同。
你可以先從原本的 $N$ 條弦中挑選任意多條，使得任兩條被保留的弦都不相交（其餘刪除），接著再自由新增一條弦。
問操作完成後，弦與弦之間的交點數最多能是多少。

Constraints

約束條件

$1\le N\le 2\times 10^5$
$1\le A_i,B_i\le 2N$
$A_1,\dots,A_N,B_1,\dots,B_N$ 兩兩不同

思路：破環成鏈 + 二維 LIS

核心觀察：相交的幾何等價條件

題目要求在圓上保留一組互不相交的弦，並加入一條新弦，使得新弦與這些保留的弦交點數最大。
由於保留的弦本身互不相交，若一條新弦能同時貫穿它們，這意味著在圓上，這些被保留的弦必須呈現層層嵌套（包含）的結構。
換句話說，如果我們沿著新弦的兩個端點將圓剪開並拉平成一條直線，這些被保留的弦會變成一組嚴格嵌套的區間（即外層區間完全包覆內層區間）。
因此，原問題等價於：在給定的弦中，找出最多能有幾條弦形成互相嵌套的關係。

兩種表示不是兩套答案

一條弦可以把圓切成兩段弧，所以同一條弦可以被表示成兩種區間。
因此看似我們可以選取兩套不相交的嵌套，但換個角度來看，在另一種區間表示下，這兩組嵌套其實能被視為是同一組。

圖示說明

abc410G

圖中的紫色和藍色嵌套，看似是兩套不同的嵌套鏈，但如果將藍色的那組用另外一條弧來表示，就會發現也能被視為是紫色的那組嵌套鏈。

1. 破環成鏈

為了處理圓上的嵌套關係，我們可以使用「破環成鏈」的技巧將圓展開為直線。
對於每一條給定的弦，假設其兩個端點為 $u$ 和 $v$ （假設 $u < v$ ），它實際上把圓分成了兩段弧。在展開的直線上，這條弦可以有兩種區間表示方式：

不跨越起點的區間： $[u, v]$
跨越起點的區間： $[v, u + 2N]$

我們將這 $N$ 條弦各自轉成兩個區間表示，因此總共得到 $2N$ 個區間。接下來只要在這些區間中，找到一條最長的「嚴格嵌套鏈」，其長度就對應到最多能被新弦同時交到的弦數。

2. 轉化為最長遞增子序列 (LIS)

在直線上，一組區間要形成嚴格嵌套，必須滿足：

左邊界嚴格遞增
右邊界嚴格遞減

這是一個經典的二維偏序問題，類似 354. Russian Doll Envelopes，只是第二維從 LIS 變成 LDS。

我們可以透過以下步驟求解：

排序：將所有區間按照「左邊界」由小到大排序。
尋找 LDS：在排序後的區間列表中，針對「右邊界」尋找最長嚴格遞減子序列（LDS, Longest Decreasing Subsequence）。

但顯然 $O(N^2)$ 的時間複雜度太高，因此需要轉換為將值域或先前結果作為狀態的優化 DP，這裡採用後者，也就是大家熟知的利用二分搜尋的 LIS 方法，詳細內容這裡不展開，可以見參考資料的影片。
另外將求 LDS 可以倒過來求 LIS，或是直接將右邊界取負後求 LIS，這樣就能用標準的 LIS 二分搜尋方法來維護狀態。

合法性保證

題目保證所有端點兩兩不同，因此每個區間的左邊界也都不同，這樣在依左邊界排序時，不需要另外處理「左邊界相同」的情況。
同一條弦會被展開成兩個區間： $[u, v]$ 與 $[v, u + 2N]$ 。這兩個區間無法同時出現在同一條「嚴格包含鏈」中（長度與包含關係會矛盾）。
因此，求得的最長嵌套區間序列，必然對應到圓上一組端點互異且可同時保留的弦。

複雜度分析

時間複雜度： $\mathcal{O}(N\log N)$ ，其中 $N$ 為弦的數量。主要時間花費在對 $2N$ 個區間進行排序，以及長度為 $2N$ 的 LIS 二分搜尋。
空間複雜度： $\mathcal{O}(N)$ ，用於儲存轉換後的區間陣列以及 LIS 的狀態陣列。

參考資料

动态规划到底是只属于天才的灵光乍现？还是普通人也可以模仿学习？以【最长递增子序列】这个经典模型，来看那些突然蹦出来的状态到底是怎么来的

Code

from bisect import bisect_left


def solve():
    n = int(input())
    A = []
    for _ in range(n):
        l, r = map(int, input().split())
        l, r = min(l, r), max(l, r)
        A.append((l, r))
        A.append((r, l + (n << 1)))
    A.sort()
    f = []
    for _, r in A:
        idx = bisect_left(f, -r)
        if idx == len(f):
            f.append(-r)
        else:
            f[idx] = -r
    print(len(f))


if __name__ == "__main__":
    solve()

寫在最後

PROMPT

這裡什麼都沒有。