最长下降子序列

1432. Colorful inversion

给定序列 $\{a_i\}$，对于每个 $i$，输出以 $a_i$ 结尾的最长下降子序列长度。

限制：$1 \leq n \leq 10^5, 1 \leq a_i \leq 10 ^ 6$。

下降、上升、不下降、不上升？

请注意以上限制条件的不同会在细节上有不同，请仔细考虑。

动态规划

我们用 $f_i$ 表示以 $i$ 结束的最长下降序列最长能有多长，转移方程为

\[ f_i = \max\{f_j | j < i, a_j > a_i\} + 1.\]

边界条件如何设置？

令 $a_0 = +\infty, f_0 = 0$。

使用二分优化

应用二分是能在单调的序列上快速查找，我们需要寻找问题的 单调性。

假设我们已经求出了 $j = 1, \dots, i - 1$ 的答案。现在，考虑反向维护每个 $f_j$ 对应的 $a_j$ 的最大取值：我们令 $g_{i,k}$ 表示 $i$ 之前长度为 $k$ 的下降子序列结尾最大能是谁。此时，我们的转移方程变成了：

\[ f_i = \max \{k | g_{i,k} > a_i\} + 1. \]

证明：$g_k$ 单调下降。

因为每个 $k$ 子序列删掉最后一个元素都是 $k - 1$ 子序列。

使用 $g_k$ 的单调性，我们可以直接二分搜索上面最大的满足条件的元素，来更新 $f_i$。

int l = 0, r = maxk;
while (l < r) {
    int mid = (l + r + 1) / 2; // 上取整
    if (g[mid] > a[i]) l = mid; // mid <= maxk
    else r = mid - 1; // mid > maxk
}
// l == r == maxk

二分边界

注意可能导致二分边界爆炸的情况，包括上下取整、mid 是否更新答案、$l, r$ 初始值等。

尽管本题不需要，在 $r$ 很大或者 $l$ 为负数时，你可能需要类似 l + (r - l) / 2 的写法来防止爆 int，或者确保除法向下取整。

二分查错

二分是优化。出错而无法确定问题时，请先考虑去掉优化，例如写一个直接扫描数组替换掉二分。这样可以更准确地定位问题，防止对查错无从下手。

如何在 $f_i$ 更新后，让 $g_{i}$ 更新为 $g_{i + 1}$ 呢？注意到，此时可能更新 $g$ 的只有刚刚求出的这个子序列。因此，更新为 $$ g_{i + 1, k} = \begin{cases} \max \{a_i, g_{i, k}\} & k = f_i \\ g_{i, k} & \text{otherwise} \end{cases} $$ 可以省去 $g$ 的第一维，直接对 $g[f_i]$ 进行更新。