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 值已經算出,因此合併必須放在遞歸右區間之前。) 而這個過程是可以離線的。 合併過程的複雜度是 ,總的複雜度是 。 cdq 分治: https://gist.github.com/lychees/66c22315b8235d61722b#file-cdq-cpp

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