D. 在波罗的海国家搭便车 详细题解

问题重述

给定 $n$ 个区间 $[l_i, r_i]$，需要为每个区间选择一个整数点 $x_i \in [l_i, r_i]$，然后找出一个最长的子序列，使得子序列的编号严格递增，且选择的点也严格递增。求这个最长子序列的长度。

等价于：在按顺序处理区间时，每个区间可以选择一个点，要求选出的点序列严格递增，求最多能选多少个区间。

关键观察

观察 1：转化为最长上升子序列问题

这个问题类似于最长上升子序列（LIS），但每个位置可以选择的值是一个区间，而不是固定值。

定义 $dp[i]$ 表示长度为 $i$ 的严格递增子序列的最后一个元素的最小可能值。

经典 LIS 的 $dp$ 数组具有严格递增的性质：

观察 2：处理新区间 $[l, r]$

当我们考虑新区间 $[l, r]$ 时，有两种可能的转移：

第一种转移：以 $l$ 作为新的最后一个元素

设 $i$ 是满足 $dp[i] < l$ 的最右位置，那么我们可以构造一个长度为 $i+1$ 的子序列，以 $l$ 结尾。由于 $i$ 是最右位置，有 $dp[i+1] \ge l$，因此：

第二种转移：利用区间内的其他值

设 $j$ 是满足 $dp[j] < r$ 的最右位置。对于任意 $k \le j$，我们可以将 $dp[k]$ 增加 $1$（因为可以选择 $dp[k]+1$ 作为下一个值，只要它不超过 $r$）。由于 $dp$ 严格递增，有：

这意味着对于所有 $k \le j$，$dp[k+1]$ 可以被更新为 $\min(dp[k+1], dp[k]+1) = dp[k]+1$。

实际上，这相当于将 $dp[2]$ 到 $dp[j+1]$ 这段区间的值整体加 $1$。

观察 3：操作总结

处理新区间 $[l, r]$ 时，需要执行以下操作：

1. 找到位置 $i$，使得 $dp[i] < l \le dp[i+1]$，然后设置 $dp[i+1] = l$
2. 找到位置 $j$，使得 $dp[j] < r \le dp[j+1]$，然后将 $dp[2]$ 到 $dp[j+1]$ 全部加 $1$
3. 由于 $dp$ 长度会增加，需要删除超出部分

数据结构选择

由于 $n \le 3 \times 10^5$，且需要支持：

• 按值分裂（split）
• 区间加
• 合并（merge）
• 查找最左端点的值

使用笛卡尔树（Treap） 来实现这些操作。

算法步骤

1. 初始化：

   • 创建 Treap，初始包含一个节点 $dp[0] = 0$
   • 为了便于处理，预先加入足够多的无穷大节点

2. 对每个区间 $[l, r]$ 按顺序处理：

   a. 将 Treap 按值 $l$ 分裂成 $L$ 和 $R$（$L$ 中所有值 $< l$，$R$ 中所有值 $\ge l$）

   b. 将 $R$ 按值 $r$ 分裂成 $M$ 和 $R$（$M$ 中所有值 $< r$，$R$ 中所有值 $\ge r$）

   c. 对 $M$ 中所有值加 $1$（区间加操作）

   d. 找到 $R$ 中最左边的值 $cnt$（即 $dp[i+1]$），将 $R$ 分裂成前 $cnt$ 个节点和剩余部分

   e. 合并：$L$ + 新节点（值为 $l$） + $M$ + 剩余部分

3. 统计结果：

   • 遍历 Treap，统计值不为无穷大的节点数，减 $1$ 即为答案（减去初始的 $0$）

时间复杂度

• 每个区间处理：$O(\log n)$ 次 Treap 操作
• 总时间复杂度：$O(n \log n)$

完整代码实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 5;
const int MAXN = 300005;

// Treap 节点结构
struct node {
    int prior;      // 优先级
    int dp;         // 节点值
    int add;        // 懒标记（区间加）
    node *l, *r;    // 左右子节点
    
    node(int x) {
        prior = (rand() << 15) | rand();  // 随机优先级
        dp = x;
        l = r = NULL;
        add = 0;
    }
};

typedef node* pnode;

// 下传懒标记
void push(pnode T) {
    if (!T || T->add == 0) return;
    
    T->dp += T->add;
    if (T->l) T->l->add += T->add;
    if (T->r) T->r->add += T->add;
    T->add = 0;
}

// 合并两个 Treap
void merge(pnode& T, pnode L, pnode R) {
    if (!L) {
        T = R;
        return;
    }
    if (!R) {
        T = L;
        return;
    }
    
    push(L);
    push(R);
    
    if (L->prior > R->prior) {
        merge(L->r, L->r, R);
        T = L;
    } else {
        merge(R->l, L, R->l);
        T = R;
    }
}

// 按值分裂：L 包含值 < value 的节点，R 包含值 >= value 的节点
void split(pnode T, int value, pnode& L, pnode& R) {
    if (!T) {
        L = R = NULL;
        return;
    }
    
    push(T);
    
    if (T->dp >= value) {
        split(T->l, value, L, T->l);
        R = T;
    } else {
        split(T->r, value, T->r, R);
        L = T;
    }
}

// 查找最左边的节点的值
int findBegin(pnode T) {
    push(T);
    if (!T->l) return T->dp;
    return findBegin(T->l);
}

// 统计有效节点数（值不为 INF 的节点）
int countValid(pnode T) {
    if (!T) return 0;
    push(T);
    return countValid(T->l) + countValid(T->r) + (T->dp < INF ? 1 : 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    srand(time(0));
    
    int n;
    cin >> n;
    
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    
    // 初始化 Treap，加入初始节点 0 和足够多的 INF 节点
    pnode T = new node(0);
    for (int i = 1; i <= n + 5; i++) {
        pnode newNode = new node(INF + i);
        merge(T, T, newNode);
    }
    
    pnode L = NULL, M = NULL, R = NULL, rubbish = NULL;
    
    for (int j = 0; j < n; j++) {
        int l = a[j].first;
        int r = a[j].second;
        
        // 按 l 分裂
        split(T, l, L, R);
        
        // 按 r 分裂 R
        split(R, r, M, R);
        
        // M 中的所有值加 1
        if (M) {
            M->add += 1;
        }
        
        // 找到 R 中最左边的值
        int cnt = findBegin(R);
        
        // 删除 R 中前 cnt 个节点（实际上需要删除到 cnt 位置）
        split(R, cnt + 1, rubbish, R);
        
        // 合并：L + 新节点(l) + M + R
        merge(T, L, new node(l));
        merge(T, T, M);
        merge(T, T, R);
    }
    
    // 答案 = 有效节点数 - 1（减去初始的 0）
    int ans = countValid(T) - 1;
    cout << ans << "\n";
    
    return 0;
}

代码说明

1. 节点结构：

   • dp：存储 $dp$ 值
   • add：懒标记，用于区间加操作
   • prior：随机优先级，保证 Treap 平衡

2. 核心操作：

   • push：下传懒标记，更新节点值
   • split：按值分裂 Treap
   • merge：合并两个 Treap

3. 处理流程：

   初始: T = [0, INF, INF+1, INF+2, ...]
   
   对每个区间 [l, r]:
     1. 分裂: T = L (< l) + R (>= l)
     2. 分裂: R = M (< r) + R (>= r)
     3. M 中所有值加 1
     4. 找到 R 的最小值 cnt
     5. 分裂 R: 删除前 cnt 个节点
     6. 合并: L + [l] + M + R
   

4. 为什么这样正确：

   • $M$ 中的值对应 $dp[2]$ 到 $dp[j+1]$，将它们加 $1$ 实现了第二种转移
   • 插入新节点 $l$ 实现了第一种转移
   • 删除操作保证了 $dp$ 数组的严格递增性质

总结

本题的核心技巧：

1. 将问题转化为带区间选择的 LIS 问题
2. 使用 $dp[i]$ 表示长度为 $i$ 的递增子序列的最小末尾值
3. 发现处理新区间时的两种转移可以简化为区间加操作
4. 使用 Treap 维护 $dp$ 数组，支持分裂、合并、区间加操作
5. 时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$