Codeforces 🟣 CF809D. Hitchhiking in the Baltic States

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

🔗 CF809D Hitchhiking in the Baltic States

Problem Statement

題目簡述

給定 $n$ 個區間 $[l_i, r_i]$，你可以為每個區間選擇一個整數 $x_i \in [l_i, r_i]$。
在每個區間選一個值，求出 最長遞增子序列(Longest Increasing Subsequence, LIS) 的長度。

Constraints

約束條件

• $1 \le n \le 3 \cdot 10^5$
• $1 \le l_i \le r_i \le 10^9$

---

思路：FHQ Treap 維護 LIS 狀態

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

狀態定義

在經典的 LIS 問題中，我們通常會維護一個陣列，其中第 $j$ 個元素表示「長度為 $j$ 的嚴格遞增子序列中，結尾元素的最小值」。

狀態的單調性

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

狀態轉移分析

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

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

1. 如果 $prev < l_i$，我們可以直接選擇區間的下界 $l_i$。
2. 如果 $l_i \le prev < r_i$，由於必須嚴格遞增，新的值至少要是 $prev+1$，而在區間內能選到的最小值就是 $prev+1$。
3. 如果 $prev \ge r_i$，則無法從這個狀態擴展（因為區間內的所有數都 $\le prev$）。

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

轉移的整體影響

由於狀態陣列（每個長度的「最小可能結尾值」）是嚴格遞增的，我們可以把目前所有有限的狀態值視為一個遞增序列，並依照區間邊界 $l_i, r_i$ 把它切成三段來看它會怎麼被更新：

1. $< l_i$ 的部分：
   這些結尾值太小，若要接上這個區間並保持嚴格遞增，最小能選到的值一定是 $l_i$。因此它們提供的「候選新結尾」全部都相同（都是 $l_i$），最後只需要保留一個最優的結果，也就是插入一個 $l_i$。
2. 落在 $[l_i, r_i)$ 的部分：
   對於這段中的任一結尾值 $v$，要嚴格遞增就必須選至少 $v+1$；而因為 $v < r_i$，所以 $v+1$ 仍落在區間內。換句話說，這一整段的狀態值會被全部加 1。
3. $\ge r_i$ 的部分：
   這些結尾值已經不小於區間上界，區間內不存在比它更大的數可選，因此它們無法產生有效轉移。此外，第二段的整體 $+1$ 可能會把某些值推到 $\ge r_i$ 的區域，造成原本「最小的 $\ge r_i$ 狀態」不再需要，等價於要刪除第一個 $\ge r_i$ 的狀態值（若存在）。

核心結論

綜合上述三個部分的變化，從整體的角度來看，狀態序列的更新可以濃縮成三個動作：

1. 將所有落在 $[l_i, r_i)$ 的狀態值全部加 1。
2. 刪除第一個 $\ge r_i$ 的狀態值（若存在）。
3. 插入一個 $l_i$。

最後狀態序列的長度即為當前可達到的最長 LIS 長度。

這個結論和 CF2121H Ice Baby 幾乎相同，兩者的差別在於：該題處理的是 LNDS（非嚴格遞增），只需「插入 $l$」與「刪除第一個 $> r$」即可，不需要區間加一。

為什麼需要 FHQ Treap？

因為需要對狀態序列中的一段區間進行整體加 1，單純使用 multiset 或一般平衡樹無法高效支援帶 lazy 標記的區間修改。
FHQ Treap（可持久化無旋 Treap）恰好滿足所有需求。

FHQ Treap 核心操作

• split(root, key)：將樹拆成「$\text{val} < \text{key}$」與「$\text{val} \ge \text{key}$」兩部分
• merge(a, b)：合併兩棵樹，使用前需保證 $a$ 中所有值 $\le b$ 中所有值
• apply(root, val)：對整棵子樹加上 lazy 標記
• popmin(root)：刪除樹中的最小值

---

複雜度分析

• 時間複雜度：$\mathcal{O}(n \log n)$，每個區間做常數次分裂、合併、懶惰更新與刪除操作，在隨機 priority 的保證下，每次操作的平均時間複雜度為 $\mathcal{O}(\log n)$。
• 空間複雜度：$\mathcal{O}(n)$，狀態序列最多長度為 $n$。

類題

• 🔵 P4303 [AHOI2006] 基因匹配
• 🔵 CF2121H Ice Baby
  本題的簡化版本，差別在從 LIS 變成 LNDS，可以直接使用 multiset 來維護狀態。

---

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'

class FHQTreap {
public:
    class Node {
    public:
        Node *left, *right;
        int sz;
        uint32_t pri;   // Treap 的 heap priority
        i64 val, lazy;  // val: BST key, lazy: lazy tag
        Node(i64 val, uint32_t pri)
            : left(nullptr),
              right(nullptr),
              sz(1),
              pri(pri),
              val(val),
              lazy(0) {}
    };

private:
    vector<unique_ptr<Node>> pool;
    mt19937 rng;

public:
    explicit FHQTreap(int reserveNodes = 0)
        : rng(static_cast<uint32_t>(
              chrono::steady_clock::now().time_since_epoch().count())) {
        pool.reserve(reserveNodes + 5);
    }

    int size(Node* root) const {
        return root ? root->sz : 0;
    }

    // 建立一個新節點
    Node* make(i64 value) {
        pool.emplace_back(make_unique<Node>(value, rng()));
        return pool.back().get();
    }

    // 由左右子樹資訊更新目前節點
    void pushup(Node* root) {
        if (!root) return;
        root->sz = size(root->left) + size(root->right) + 1;
    }

    // 對整棵子樹套用加法標記
    void apply(Node* root, i64 value) {
        if (!root) return;
        root->val += value;
        root->lazy += value;
    }

    // 將 lazy tag 下推到左右子節點
    void pushdown(Node* root) {
        if (!root || root->lazy == 0) return;
        i64 tag = root->lazy;
        apply(root->left, tag);
        apply(root->right, tag);
        root->lazy = 0;
    }

    // 依照 key 將 Treap 分裂成兩棵
    // - a：所有 val < key 的節點
    // - b：所有 val >= key 的節點
    pair<Node*, Node*> split(Node* root, i64 key) {
        if (!root) return {nullptr, nullptr};
        pushdown(root);
        if (root->val < key) {
            auto [a, b] = split(root->right, key);
            root->right = a;
            pushup(root);
            return {root, b};
        } else {
            auto [a, b] = split(root->left, key);
            root->left = b;
            pushup(root);
            return {a, root};
        }
    }

    // 合併兩棵 Treap
    // 使用前必須保證：a 中所有值 <= b 中所有值
    Node* merge(Node* a, Node* b) {
        if (!a || !b) return a ? a : b;
        if (a->pri < b->pri) {
            pushdown(a);
            a->right = merge(a->right, b);
            pushup(a);
            return a;
        } else {
            pushdown(b);
            b->left = merge(a, b->left);
            pushup(b);
            return b;
        }
    }

    // 插入一個值
    // 若 Treap 中已存在相同值，仍會插入新節點
    Node* insert(Node* root, i64 value) {
        auto [a, b] = split(root, value);
        Node* mid = make(value);
        return merge(merge(a, mid), b);
    }

    // 刪除一個值
    // 若存在多個相同 value，只會刪除其中一個
    // 若 value 不存在，Treap 內容不變
    Node* erase(Node* root, i64 value) {
        if (!root) return nullptr;
        pushdown(root);
        if (root->val == value) return merge(root->left, root->right);
        if (value < root->val)
            root->left = erase(root->left, value);
        else
            root->right = erase(root->right, value);
        pushup(root);
        return root;
    }

    // 對所有 val 屬於 [l, r) 的節點加上 value
    // 注意：這個操作會直接修改節點的 val
    // 使用時必須確保更新後仍然不破壞 Treap 的 BST 順序
    Node* update(Node* root, i64 l, i64 r, i64 value) {
        auto [a, b] = split(root, l);
        auto [c, d] = split(b, r);
        apply(c, value);
        return merge(merge(a, c), d);
    }

    // 刪除 Treap 中的最小值
    Node* popmin(Node* root) {
        if (!root) return nullptr;
        pushdown(root);
        if (!root->left) return root->right;
        root->left = popmin(root->left);
        pushup(root);
        return root;
    }

    // 刪除 Treap 中的最大值
    Node* popmax(Node* root) {
        if (!root) return nullptr;
        pushdown(root);
        if (!root->right) return root->left;
        root->right = popmax(root->right);
        pushup(root);

        return root;
    }

    // 取得 Treap 中的最小值
    // 使用前必須保證 root != nullptr
    i64 front(Node* root) {
        pushdown(root);
        while (root->left) {
            root = root->left;
            pushdown(root);
        }
        return root->val;
    }

    // 取得 Treap 中的最大值
    // 使用前必須保證 root != nullptr
    i64 back(Node* root) {
        pushdown(root);
        while (root->right) {
            root = root->right;
            pushdown(root);
        }
        return root->val;
    }
};

void solve() {
    int n, l, r;
    cin >> n;

    FHQTreap tr(n);

    using Node = FHQTreap::Node;

    Node* f = nullptr;

    for (int i = 0; i < n; i++) {
        cin >> l >> r;

        // A: < l, B: >= l
        auto [A, B] = tr.split(f, l);
        // C: [l, r), D: >= r
        auto [C, D] = tr.split(B, r);

        // [l, r) 這段全部 +1
        C = tr.update(C, l, r, 1);  // 其實 tr.apply(C, 1) 就可以了

        // 刪掉第一個 >= r 的 DP 值
        D = tr.popmin(D);

        // 插入新的 l
        C = tr.insert(C, l);

        // 合併
        f = tr.merge(tr.merge(A, C), D);
    }

    cout << tr.size(f) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

---

寫在最後

PROMPT

這裡什麼都沒有。