[QOJ4629] Longest Increasing Subsequence

[QOJ4629] Longest Increasing Subsequence

给定长度为 \(n\) 的正整数递增序列 \(a\)，进行若干次如下操作：

• 记序列 \(a\) 排序后的结果为序列 \(s\)。
• 按序遍历 \(i=1,\dots,n-1\)，如果 \(s_i \neq s_{i+1}-1\)，则在序列 \(a\) 的末尾加上 \(\left\lfloor \dfrac{s_i+s_{i+1}}{2}\right\rfloor\)。
• 如果序列 \(a\) 没有变化，结束操作，否则回到第一步。

求最终序列 \(a\) 的最长上升子序列。

\(n \le 10^5, a_n \le 10^{18}\)

容易发现最终的序列为排列，长度为 \(a_{n}\)，肯定是没法做的。

考虑到这个问题是对一个二叉搜索树森林按层遍历的结果，我们考虑该结构的特殊性质。

画出结构，清晰起见，对于最初的序列 \(a\) 放在最上面，相邻两个数连向对应的搜索树：

这是一个理想的结构，二叉搜索树全是满的，对应序列为 \([1, 5, 13]\)。

相当于走一条最长的路径，走法只有：在同层节点之间从左往右走，往更深的右儿子节点走，或者是跨越搜索树走向更深节点。

注意到可以以深度和搜索树编号为阶段划分问题，设 \(f_{i, j}\) 表示 \(a_{i}\) 与 \(a_{i-1}\) 夹的搜索树，走到第 \(j\) 层的最右节点，所走步数的最大值。

考虑满二叉树的情况，容易发现，每棵搜索树上一定是走到该深度的极右节点是最好的。如果在该层是深度为 \(d\)，则上一棵搜索树最终一定是走到 \(d\) 的深度，或者高度不足 \(d\) 而只走到最深层。由每个深度的节点数递增可证。

所以有转移：

\[f_{i, j} = f_{i-1, k}+c(i, j) (k \le j) \]

其中 \(c(i,j)\) 表示 \(i\) 树中第 \(j\) 层的节点个数。

这个转移足以应付所有搜索树均为满二叉树的情况。考虑一般情况，会在满二叉树上挂若干个叶子。

在这种情况下就不一定在最后一层直接走通，当然，如果最后一层节点非常多，也完全可以直接走通。

所以说 dp 还得特判一下这种情况，其实很简单，\(f_{i, d} \gets f_{i,d-1}+1\) 即可。但这里你还得注意是否能够从次深层的极右节点走到最深层（好像是一定的）。

用前缀 max 优化即可，复杂度 \(\mathcal O(n \log V)\)。