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

🔗 🔵 CF2121H. Ice Baby

Problem Statement

題目簡述

給定兩個長度為 $n$ 的陣列 $l$ 和 $r$ 。
對於每個 $k \in [1, n]$ ，考慮所有長度為 $k$ 的陣列 $a$ ，滿足 $l_i \le a_i \le r_i$ ( $1 \le i \le k$ )。
請求出在所有可能的陣列 $a$ 中，最長非遞減子序列 (LNDS) 的最大長度。

Constraints

約束條件

$1 \le t \le 10^4$
$1 \le n \le 2 \cdot 10^5$
$1 \le l_i \le r_i \le 10^9$
$\sum n \le 2 \cdot 10^5$

思路：資料結構維護 LIS 狀態

這是一道典型的利用資料結構優化動態規劃的題目。我們可以從最長遞增子序列（LIS）的經典解法出發，思考如何將其擴展到區間的情況。

狀態定義

在經典的 LIS 問題中，我們通常會維護一個陣列，其中第 $j$ 個元素表示「長度為 $j$ 的遞增子序列中，結尾元素的最小值」。
我們將這個概念套用到本題：定義一個狀態陣列，其第 $j$ 個元素代表長度為 $j$ 的非遞減子序列中，結尾元素的最小值。

狀態的單調性

顯然，這個狀態陣列必定是一個單調不遞減的序列。長度越長的子序列，其結尾元素的最小值必然大於等於較短子序列的結尾元素最小值。

狀態轉移分析

當我們依序處理每個區間 $[l_i, r_i]$ 時，考慮它能如何更新我們的狀態陣列。
對於任意長度 $j$ ，我們可以嘗試從長度為 $j-1$ 的子序列擴展而來。為了讓新的結尾元素盡可能小，我們應該在區間 $[l_i, r_i]$ 中挑選一個大於等於前一個元素的最小值。

具體來說，假設前一個元素的值為 $prev$ ：

如果 $prev \le l_i$ ，我們可以直接選擇區間的下界 $l_i$ 。
如果 $l_i < prev \le r_i$ ，我們必須選擇 $prev$ 本身（因為要滿足非遞減的條件）。
如果 $prev > r_i$ ，則無法從這個狀態擴展（因為區間內的所有數都太小了）。

綜合起來，我們挑選的新結尾元素會是 $\max(prev, l_i)$ ，前提是 $prev \le r_i$ 。
接著，我們將這個新結尾元素與原本長度為 $j$ 的結尾元素進行比較，取較小值來更新狀態。

轉移的整體影響

由於狀態陣列是單調不遞減的，我們可以根據當前區間的邊界 $l_i$ 和 $r_i$ ，將狀態陣列的值劃分為三個部分來觀察變化：

$\le l_i$ 的部分：
這些狀態即使接上新區間的數，得到的新結尾元素至少也是 $l_i$ 。因為它們原本的值就已經小於等於 $l_i$ 了，所以取最小值更新後，這部分的值完全不會改變。
$> l_i$ 且 $\le r_i$ 的部分：
- 這部分的值可以由前一個狀態轉移而來。具體來說，這段的第一個元素會被更新為 $l_i$ ，後續元素則會被更新為前一個元素的值。
- 整體來看，這部分的變化相當於將整段數值向右平移一格，並在最前面插入了 $l_i$ 。
$> r_i$ 的部分：

這部分的第一個元素（也就是 $> r_i$ 的最小元素），會因為第二部分的平移操作而被覆蓋。
而這部分的後續元素，由於前一個狀態已經大於 $r_i$ ，無法滿足非遞減條件進行有效的區間轉移，因此值不會改變。

核心結論

綜合上述三個部分的變化，從整體的角度來看，狀態陣列的改變非常單純：

插入了一個新元素 $l_i$ 。
原本在第三部分的第一個元素（也就是大於 $r_i$ 的最小元素）被擠掉了，相當於被刪除。

如果陣列中所有元素都小於等於 $r_i$ ，則沒有元素會被擠掉，這意味著最長非遞減子序列的長度成功增加了 1。

因為狀態陣列只關心值的集合而不保留順序索引，平移效果會自然地由後續的插入與刪除操作體現。

資料結構維護

但在陣列中插入元素的複雜度是 $\mathcal{O}(n)$ ，如果直接模擬整個狀態陣列的變化，對於 $n$ 個區間來說，總複雜度將達到 $\mathcal{O}(n^2)$ ，這在 $n$ 高達 $2 \cdot 10^5$ 的情況下是不可行的。

既然我們只需要進行「插入元素」和「尋找並刪除大於某個值的最小元素」這兩種操作，我們可以使用支援動態排序的資料結構來維護這個狀態陣列。

在 C++ 中，可以使用 std::multiset。
在 Python 中，可以使用 sortedcontainers.SortedList（或自行實作平衡樹等替代方案）。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，對於每個區間，我們在 multiset 中進行常數次查詢、插入和刪除操作，每次操作的時間複雜度為 $\mathcal{O}(\log n)$ 。
空間複雜度： $\mathcal{O}(n)$ ，multiset 最多儲存 $n$ 個元素。

類題

🔵 P4303 [AHOI2006] 基因匹配
🟣 CF809D Hitchhiking in the Baltic States
本題的加強版本，差別在從 LNDS 變成 LIS，這對於使用的資料結構提出了更高的要求。

Code

Warning

這份 Python 程式碼使用 sortedcontainers.SortedList 方便測試，但其實 Codeforces 不支援這個套件。
若要正式提交，可以直接複製 SortedList 的原始碼，也能自行實作可支援插入、刪除、排名查詢的有序結構。

from sortedcontainers import SortedList

def solve():
    n = int(input())

    ans = []
    f = SortedList()
    for _ in range(n):
        l, r = map(int, input().split())
        idx = f.bisect_right(r)
        if idx != len(f):
            f.pop(idx)
        f.add(l)
        ans.append(len(f))
    print(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。