题目分析

这是一个带有约束的最大选择问题。每株郁金香有两个约束：

• 选择第 i 株时，左侧 l_i 株不能选
• 选择第 i 株时，右侧 r_i 株不能选

需要找到在满足所有约束的情况下，最多能选择的郁金香数量。

算法思路

核心思想

使用动态规划 + 树状数组优化：

1. 动态规划状态：f[i] 表示以第 i 株郁金香结尾的最优选择方案大小
2. 树状数组优化：快速查询前缀最大值
3. 延迟更新：考虑右侧约束对后续选择的影响

关键观察

• 如果选择郁金香 i，那么它左侧的 l_i 株不能选
• 如果选择郁金香 i，那么它右侧的 r_i 株不能选（影响后续选择）
• 问题转化为：在满足约束的条件下，选择最多的郁金香

代码详解

数据结构定义

const int N = 200010;
int n, l[N], r[N];      // 输入的限制条件
int tr[N], f[N];        // 树状数组和DP数组
int ans;                // 最终答案
vector<int> upd[N];     // 延迟更新列表

树状数组操作

int lowbit(int i) {
    return i & -i;  // 获取最低位的1
}

void update(int x, int k) {
    // 更新位置x，维护前缀最大值
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] = max(tr[i], k);
}

int query(int x) {
    // 查询前缀[1,x]的最大值
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res = max(res, tr[i]);
    return res;
}

主算法流程

cin >> n;

// 读取输入（1-indexed）
for (int i = 1; i <= n; i++)
    cin >> l[i] >> r[i];

// 动态规划
for (int i = 1; i <= n; i++) {
    // 计算f[i]：以i结尾的最优方案
    if (i - 1 <= l[i]) {
        // 情况1：左侧郁金香数量不足l[i]
        // 可以直接选择i，前面不需要考虑
        f[i] = 1;
    } else {
        // 情况2：需要从左侧选择合适的郁金香
        // 只能选择位置在[1, i-l[i]-1]范围内的郁金香
        f[i] = query(i - l[i] - 1) + 1;
    }
    
    // 更新答案
    ans = max(ans, f[i]);
    
    // 延迟更新：记录f[i]何时可以影响其他郁金香
    // 由于选择i会禁止右侧r[i]株，所以f[i]在i+r[i]之后才有效
    upd[min(n, i + r[i])].push_back(i);
    
    // 处理到期的更新
    for (int j : upd[i])
        update(j, f[j]);  // 更新树状数组
}

cout << ans << "\n";

算法原理

动态规划状态转移

定义 f[i] 为：以郁金香 i 作为最后选择的郁金香时，最多能选择的数量

转移方程分析：

1. 如果选择郁金香 i，左侧 l_i 株不能选
2. 所以前一个选择的郁金香必须在位置 ≤ i-l_i-1
3. 因此：f[i] = max{f[j]} + 1，其中 j ≤ i-l_i-1

特殊情况：

• 如果 i-1 ≤ l[i]：左侧郁金香数量不足 l[i]
• 那么可以直接选择 i，不需要考虑前面：f[i] = 1

树状数组的作用

普通的DP需要遍历所有 j ≤ i-l_i-1 来求最大值，时间复杂度 O(n²)，无法接受。

树状数组 tr 维护：

• tr[x] = 所有 j ≤ x 的 f[j] 的最大值
• 支持 O(log n) 查询前缀最大值

延迟更新的必要性

问题：如果选择郁金香 i，右侧 r_i 株不能选

• 这意味着 f[i] 不能作为位置 j ∈ [i+1, i+r_i] 的前驱
• 只有当 j > i+r_i 时，才能考虑 f[i]

解决方案：

• 将 f[i] 的更新延迟到位置 i+r_i
• upd[t] 存储所有需要在位置 t 更新的 f 值
• 当处理到位置 i 时，执行 upd[i] 中的所有更新

复杂度分析

时间复杂度

• 读取输入：O(n)
• 主循环：O(n) 次迭代
• 树状数组操作：每次 O(log n)
• 延迟更新：每个 f[i] 更新一次，总 O(n log n)
• 总复杂度：O(n log n)

空间复杂度

• 输入数组：O(n)
• DP数组：O(n)
• 树状数组：O(n)
• 更新列表：O(n)

样例分析

样例1

输入：

3
0 3
1 0
1 0

执行过程：

1. i=1: l[1]=0, r[1]=3 → f[1]=1, 更新到 upd[4]
2. i=2: l[2]=1, r[2]=0 → 查询 query(0)=0, f[2]=1, 更新到 upd[2]
3. i=3: l[3]=1, r[3]=0 → 查询 query(1)=0, f[3]=1, 更新到 upd[3]
4. 答案：max(1,1,1)=1

样例2

输入：

5
0 3
1 0
0 1
2 0
1 0

算法能找到最优解 f[1]=1, f[2]=2, f[3]=3, f[4]=1, f[5]=2 最终答案：3

算法优势

1. 高效性：O(n log n) 解决大规模问题
2. 正确性：完整考虑左右两侧约束
3. 简洁性：代码实现简洁明了
4. 通用性：适用于各种约束条件

关键技巧

1. 1-indexed处理：方便树状数组操作
2. 前缀最大值查询：树状数组优化DP
3. 延迟更新机制：处理右侧约束
4. 边界处理：min(n, i+r[i]) 防止数组越界