Brief description:

三维 LIS。

Analysis:

先对一个轴进行排序，于是转换成二维 LIS 问题，但是转移时必须保证 j < i。

算法一：kd 树

这种做法比较裸。支持插入 (x_i, y_i) 的点、和查询 y_j <= y_i && z_j <= z_i 范围内所有的点即可。

算法二：cdq 分治

考虑当前点 i，我们尝试对所有 $y_j <= y_i$ 的点建立一种数据结构（只需要查询前缀，树状数组即可）。 支持插入 $z_i$ 点，和查询所有 $z_j <= z_i$ 的点，就可以在 $log(n)$ 的复杂度内完成转移了。 这个问题通常的做法是离线，对 $y$ 轴排序，但是因为之前的排序，相当于我们现在被要求强制在线。 cdq 分治为我们提供了一种突破性的解决方法。 [cpp] void cdq(int l, int r){ cdq(l, m); merge(l, r); cdq(m, r); } [/cpp] merge(l, r) 表示用所有 [l, m) 中的点，去更新 [m, r) 中点。（显然要求 [l, m) 中的点的 dp 值已经算出，因此合并必须放在递归右区间之前。） 而这个过程是可以离线的。 合并过程的复杂度是 $$O(nlogn)$$，总的复杂度是 $$O(nlog^2n)$$。 cdq 分治： https://gist.github.com/lychees/66c22315b8235d61722b#file-cdq-cpp

kd tree：
https://gist.github.com/lychees/66c22315b8235d61722b#file-kd-cpp

Posted by xiaodao
Category: 日常
Tags: cdq 分治