三维偏序下求最长“上升”序列的分治做法讲解

Part 0

用一个三维箱子最长套娃来具体化这个问题。
首先，做一个人畜无害的假设：箱子之间的三维长度彼此不同。约定每个箱子的三维用 $xyz$ 表示。

Part 1

让我们从一个 $dp$ 做法讲起：

记 $f[i]$ 表示第 $i$ 个箱子最多能做几层套娃，那么假如能装进第 $i$ 个箱子的那些箱子（记为 $j$ ）的 $f[j]$ 都已经被正确计算了 $^{[1]}$ ，那么有 $f[i]=\max(f[j])+1$ 。这样 $f[i]$ 也就被正确计算了。

这条式子可以理解为为箱子 $i$ 选择一个箱子 $j$ ，使得箱子 $i$ 直接套在 $j$ 外面。

如果按照 $x$ 升序计算箱子的 $f[i]$ ，遍历前面的所有箱子,看是否有能装进 $i$ 的，就能满足上面这个条件 $[1]$ 了。因为能装进 $i$ 的 $j$ 一定会满足 $x_j<x_i$ ，也就是会排在 $i$ 的前面，而这些箱子都是已经计算完毕的。

这样做是 $O(n^2)$ 的。

Part 2

那么把所有的箱子按 $x$ 升序排好（并且做好了离散化），接下来的问题考虑用分治-归并的方法解决。对这个序列建立一个分治结构，将这个分治的树形结构可视化，有利于接下来的陈述。

三维偏序下求最长“上升”序列的分治做法讲解

树结构的每个点代表一个区间，每个结点管辖一个区间 $[l,r]$ ，它的两个儿子分别管辖 $[l,mid]$ 和 $[mid+1,r]$ 。这是一个基础的分治结构。

还是沿用之前的 $O(n^2)$ 枚举的方法，只是把这个暴力枚举 $j$ 的过程放到这个分治结构上进行。

先假设我们的问题规模（箱子个数）只有4，也就是上图就是一个完整的分治树。

对这个树进行中序遍历，得到序列 4 2 5 1 6 3 7 。在一个点加入序列时，从右儿子区间中枚举 $i$ ，左儿子区间中枚举 $j$ ，做一次一开始的 $dp$ 贡献转移。（没有儿子就不需要转移）

那么实际上之前的做法枚举了多少对 $i-j$ ，现在还是枚举了多少对。

详细地模拟一遍（箱子编号是 1234，对应叶子编号是 4567，下面的数对为了理解方便，采用叶子编号）：

一开始所有 $f[i]$ 默认置 $1$ ，此时 $f[1]$ 已为正确值。

4 2 枚举了 4-5 已正确计算： $f[1,2]$

4 2 5 1 枚举了 4-6 5-6 4-7 5-7 已正确计算： $f[1,2,3]$

4 2 5 1 6 3 枚举了 6-7 已正确计算： $f[1,2,3,4]$

和原本做法的区别在于，现在所有的贡献全部都是在分治-归并过程中进行计算了。本质上，还是由左边贡献给右边，只是调整了一下 $i,j$ 的枚举方式。

在处理点 $2$ 的时候，已经算到了点 $5$ 直接套在 $4$ 外面的方案（记为 $4-5$ ）。然后处理点 $1$ 的时候，算了 $4-6 , 5-6$ ，以及 $4-7,5-7$ 的方案。这时候差的只是 $6-7$ 的方案，也就是右儿子管的箱子套在右儿子管的箱子外的情况，而左套左（左儿子递归时处理的）和右套左（当前点处理的）的情况都已经被算到了。右套右这种情况在递归右儿子时会计算到（处理点 $3$ 时）。

那么折腾了这么半天，从一个 $O(n^2)$ 的做法改良到了 $O(n^2)$ 的做法，~~是不是非常厉害~~。

Part 3

费这么大劲折腾上树，为的就是后面这个枚举可以通过比较简单的数据结构来加速。

考虑一个点，在处理它的左儿子到右儿子的贡献时，会有很好的性质：

（1） 左儿子管的 $x$ 全部小于右儿子管的 $x$ 。

（2） 此时左儿子内部的互相贡献在先前的递归中已经算完了（也就是说左儿子管的 $f$ 数组值都是正确的），右儿子内部的互相贡献是不用管的，以后再算。

假设左儿子管了 $L$ 个箱子，右儿子管了 $R$ 个箱子，我们现在要算的只是给这 $R$ 个箱子每个箱子从 $L$ 里找一个最优的装进去。而此时因为 $x$ 的有序，剩下的问题就只是 $y-z$ 的二维偏序问题。此时的 $R$ 个箱子就是前文的 $i$ ， $L$ 个箱子是 $j$ 。可以把问题做如下的转换：二维平面上有 $L$ 个带权点，坐标在 $(y_j,z_j)$ 点权为 $f[j]$ ，有 $R$ 个询问，每次询问点 $(y_i,z_i)$ 的左下方区域的点的最大点权。

这个问题可以用扫描线解决，把点和询问全部按照 $y$ 排序，从小到大处理，则每次要处理的问题则是在 $z_j$ 的位置新增了一个点权为 $f[j]$ 的点，或者查询位置小于 $z_i$ 的点中最大的点权。这个过程可以用树状数组加速。

那么至此，运用了这种方法加速分治-归并过程中的枚举，能做到的复杂度就是 $O(n\log^2n)$ 。

三维偏序下求最长“上升”序列的分治做法讲解

相关推荐