1.樓房重建

經典題。先轉化題意，將斜率轉化為每個點的權值，發現答案是單調遞增的。那么就是求單點修改的從第一個位置開始的最長上升子序列。

用線段樹維護兩個信息當前區間的最大值 mx，當前區間最長上升子序列長度 len。

修改時單點修改即可，考慮如何合并兩個區間的 len。可以在線段樹上二分。get(o, k) 維護當前區間以大于 k 開頭的最長上升子序列長度。

.如果當前區間的最大值小于等于k, 那么len = 0;
·如果左區間的最大值小于等于 k，直接搜索右區間；
·否則答案為 \(get(left, k) + len_o - len_{left}\) 。

時間復雜度為 \(O(n \log ^ 2n)\) 。

2.三維偏序

cdq分治。

具體做法是先將第一維排序保證 x 單調遞增，然后離散化將同一個位置的所有點的信息用一個點維護。

然后分治時按第二維排序，這樣可以保證區間內 y 有序，右區間的 x 比左區間的大。類似冒泡排序的雙指針移動，將z做值域樹狀數組。

每層遞歸統計完后也要打標記清空，保證時間復雜度為 \(O(n \log ^ 2n)\) 。