「OOI 2016 Day 1」缆车 题解

核心思路

1. 问题分析

我们需要处理 $m$ 个独立查询，每个查询修改一个位置的值后，求新序列的最长严格递增子序列 (LIS) 长度。

直接对每个查询重新计算 LIS 会超时，需要预处理。

2. 关键观察

设原序列为 $h[1 \dots n]$，修改位置 $p$ 的值为 $v$。

新序列的 LIS 可能：

1. 不包含修改位置 $p$
2. 包含修改位置 $p$

3. 预处理数组

定义：

• $f[i]$：以位置 $i$ 结尾的 LIS 长度（正向 DP）
• $g[i]$：以位置 $i$ 开始的 LIS 长度（反向 DP）
• $L$：原序列的 LIS 长度

4. 分类讨论

对于查询 $(p, v)$：

情况 1：不包含位置 $p$

此时 LIS 长度 = 原序列去掉位置 $p$ 后的 LIS 长度

但直接去掉 $p$ 可能影响 LIS，更精确地：

• 如果位置 $p$ 是原序列所有 LIS 的必经点，则去掉后长度减 1
• 否则长度不变

实际上，我们可以计算：

$$\text{ans}_1 = \max(\text{LIS不经过}p)$$

情况 2：包含位置 $p$

此时 LIS 由三部分组成：

1. $p$ 左边，结尾值 $< v$ 的最大 $f$ 值
2. 位置 $p$ 本身（贡献 1）
3. $p$ 右边，开始值 $> v$ 的最大 $g$ 值

即：

$$\text{ans}_2 = \max_{i < p, h[i] < v} f[i] + 1 + \max_{j > p, h[j] > v} g[j] $$

5. 数据结构优化

为了高效计算 $\text{ans}_2$，需要：

预处理：

• 对每个位置 $p$，维护左边所有 $(h[i], f[i])$ 的信息
• 对每个位置 $p$，维护右边所有 $(h[j], g[j])$ 的信息

查询时：

• 在左边信息中查询 $h[i] < v$ 的最大 $f[i]$
• 在右边信息中查询 $h[j] > v$ 的最大 $g[j]$

可以使用：

• Fenwick 树或线段树维护前缀/后缀最大值
• 对高度离散化处理

6. 计算不经过 $p$ 的 LIS

定义 $cnt[i]$：有多少个 LIS 经过位置 $i$

如果 $cnt[p] > 1$，则存在不经过 $p$ 的 LIS，长度 = $L$ 如果 $cnt[p] = 1$，则不经过 $p$ 的 LIS 长度 = $L - 1$

计算 $cnt[i]$ 的方法：

• 正向 DP 时记录方案数（取模避免溢出）
• 或者判断：$f[i] + g[i] - 1 = L$ 且该 $f[i]$ 值唯一

7. 算法流程

1. 预处理阶段：

   • 计算 $f[i]$：正向 LIS DP
   • 计算 $g[i]$：反向 LIS DP
   • 计算 $cnt[i]$：每个位置被多少 LIS 经过
   • 构建左边和右边的数据结构

2. 查询阶段：

   • 对于查询 $(p, v)$：
     • $\text{ans}_1 = \begin{cases} L & \text{if } cnt[p] > 1 \\ L-1 & \text{otherwise} \end{cases}$
     • $\text{ans}_2 = \text{leftMax}(p, v) + 1 + \text{rightMax}(p, v)$
     • 输出 $\max(\text{ans}_1, \text{ans}_2)$

算法实现

复杂度分析

• 预处理：$O(n \log n)$
• 每个查询：$O(\log n)$
• 总复杂度：$O((n + m) \log n)$

关键数据结构

// 左边：对于每个位置p，维护h[1..p-1]的(h, f)信息
vector<Fenwick> leftTrees;

// 右边：对于每个位置p，维护h[p+1..n]的(h, g)信息  
vector<Fenwick> rightTrees;