某岛

… : "…アッカリ~ン . .. . " .. .
September 27, 2014

HDU 4742. Pinball Game 3D

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